Day 8 of 250: LeetCode 121 Best Time to Buy and Sell Stock | Greedy State Tracking Explained

Coming Off Yesterday: From Cancellation to Minimization

On Day 7, we used the Boyer-Moore Voting Algorithm to find the majority element. The insight was about survival: track one candidate, let cancellations happen, and whatever remains at the end must be the majority. We maintained two variables and made a single pass, never looking back.

Today we carry that same single-pass, two-variable discipline into a new problem. But the logic shifts from cancellation to optimization. We are not asking which element survives. We are asking what the best decision would be at every step if we always remembered the cheapest price we had ever seen. The connection to yesterday is not the pattern name but the mindset: one controlled scan, minimal state, greedy decisions at each step.

Day 8 is LeetCode 121: Best Time to Buy and Sell Stock. It is tagged Easy and it is one of the most commonly asked problems in technical interviews, not because it is hard, but because the clean O(n) solution reveals whether a candidate understands greedy thinking and state tracking at a fundamental level.

Let us get into it.

Problem Statement

You are given an array prices where prices[i] is the price of a stock on the ith day. You want to maximize your profit by choosing one day to buy and a different future day to sell. Return the maximum profit possible. If no profit can be achieved, return 0.

Example 1:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5

Example 2:

Input:  prices = [7, 6, 4, 3, 1]
Output: 0

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

The Core Insight: The Best Buy Is Always the Minimum So Far

Here is the observation that unlocks the O(n) solution: you never gain anything by buying at a price higher than the lowest you have already seen.

If you are standing at day i trying to decide when the best buy day was, the answer is always: the day with the lowest price among all days from 0 to i - 1. It can never be beneficial to buy at a higher price when a lower one was available earlier, because the sell must happen after the buy. There is no reason to choose a worse entry point.

This means as we scan from left to right, we can always ask the question: "If I sell today, what is my profit?" And the answer is always prices[i] - minSoFar, where minSoFar is the lowest price we have seen up to this point. We just track that minimum as we go, update it whenever we see something lower, and keep a running record of the best profit we have computed.

The brute force approach checks every possible buy-sell pair: for every i, loop over every j > i and compute prices[j] - prices[i]. That is O(n^2) and completely unnecessary once you see that the best buy day for any sell day is always the minimum up to that sell day.

First Instincts vs. Correct Thinking

The very first thing most people reach for is a nested loop:

// Brute force: O(n^2) time, O(1) space
var maxProfit = function(prices) {
    let best = 0;
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            best = Math.max(best, prices[j] - prices[i]);
        }
    }
    return best;
};

This is correct, but it will time out on large inputs because it does O(n^2) work. For n = 10^5, that is 10 billion operations in the worst case.

The mental shift required is to ask: for a given sell day, do I need to check every previous buy day? No. The best previous buy day is always the cheapest one. So instead of re-scanning the past on every iteration, we just remember it. Reducing a re-scan to a remembered value is the move from O(n^2) to O(n). We are not doing anything fundamentally different: we still compare every sell candidate against the best buy candidate. We just never revisit buy candidates we have already evaluated.

Understanding the Approach

We use two variables to track everything we need.

minSoFar holds the lowest price seen from the start of the array up to and including the current index. It represents the best possible buy price for any sale we might make today or in the future. maxProfit holds the highest profit we have achieved so far across all sell days we have evaluated. It starts at 0, which represents the fallback of making no trade at all.

The rules for each step are as follows. We compute the profit we would make if we sold today: prices[i] - minSoFar. If that profit is greater than maxProfit, we update maxProfit. We then check whether prices[i] is lower than minSoFar. If it is, we update minSoFar. The order matters here: we evaluate the profit before updating the minimum, so we never accidentally "buy and sell on the same day" by using a freshly updated minimum in the same step.

Deep Dry Run: Every Step Explained

We will trace through prices = [7, 1, 5, 3, 6, 4] completely.

Initial state:

prices   = [7, 1, 5, 3, 6, 4]
indices  =  0  1  2  3  4  5

minSoFar  = 7   (first element, best buy so far)
maxProfit = 0   (no trade made yet)

Iteration 1 (i = 0):

[7]  1  5  3  6  4
 ^
 i

prices[i] = 7
profit    = 7 - 7 = 0

0 is not > maxProfit (0), no update to maxProfit.
7 is not < minSoFar (7), no update to minSoFar.

minSoFar  = 7
maxProfit = 0

Buying and selling on the same day yields zero profit. Nothing changes.

Iteration 2 (i = 1):

7  [1]  5  3  6  4
    ^
    i

prices[i] = 1
profit    = 1 - 7 = -6

-6 is not > maxProfit (0), no update to maxProfit.
1 < minSoFar (7), update minSoFar.

minSoFar  = 1
maxProfit = 0

A new low price is found. We would lose money selling today, but this becomes our new best buy candidate for all future sell days.

Iteration 3 (i = 2):

7  1  [5]  3  6  4
       ^
       i

prices[i] = 5
profit    = 5 - 1 = 4

4 > maxProfit (0), update maxProfit.
5 is not < minSoFar (1), no update to minSoFar.

minSoFar  = 1
maxProfit = 4

Selling at 5 after buying at 1 gives a profit of 4. That is the best we have seen so far.

Iteration 4 (i = 3):

7  1  5  [3]  6  4
          ^
          i

prices[i] = 3
profit    = 3 - 1 = 2

2 is not > maxProfit (4), no update to maxProfit.
3 is not < minSoFar (1), no update to minSoFar.

minSoFar  = 1
maxProfit = 4

Selling at 3 gives a profit of 2, which is worse than our current best of 4. We keep what we have.

Iteration 5 (i = 4):

7  1  5  3  [6]  4
             ^
             i

prices[i] = 6
profit    = 6 - 1 = 5

5 > maxProfit (4), update maxProfit.
6 is not < minSoFar (1), no update to minSoFar.

minSoFar  = 1
maxProfit = 5

Selling at 6 after buying at 1 gives a profit of 5. New best. This is the answer.

Iteration 6 (i = 5):

7  1  5  3  6  [4]
                ^
                i

prices[i] = 4
profit    = 4 - 1 = 3

3 is not > maxProfit (5), no update to maxProfit.
4 is not < minSoFar (1), no update to minSoFar.

minSoFar  = 1
maxProfit = 5

Selling at 4 gives only 3. Nothing improves. Loop ends.

return maxProfit = 5

Final output: 5. Correct. Buy on day 1 (price 1), sell on day 4 (price 6).

Bonus trace for Example 2: prices = [7, 6, 4, 3, 1]

Prices are strictly decreasing. At every step, prices[i] - minSoFar is either 0 (first element) or negative (every subsequent element, since each new price is lower than the previous minimum). maxProfit never rises above 0. We return 0. Correct: no trade should be made.

What Made It Work: The Deeper Why

1. The best buy for any sell day is always the minimum price seen before that day. This is the greedy axiom the whole solution rests on. For any potential sell day i, the profit is maximized by buying at the lowest possible price before day i. That lowest price is minSoFar. There is never a reason to buy at a higher price when a lower one existed earlier.

2. Evaluating profit before updating the minimum prevents buying and selling on the same day. The problem requires a different future day to sell. By checking prices[i] - minSoFar before potentially updating minSoFar to prices[i], we ensure that any sale today is measured against a buy from a strictly earlier day. The two checks happen in the correct sequence.

3. Initializing maxProfit to 0 naturally handles the no-profit case. If prices only decrease, every computed profit is negative. Since we never update maxProfit below 0, the function returns 0 as required, which represents the decision to make no trade at all.

4. A single left-to-right pass naturally enforces the buy-before-sell constraint. We never look backward. Every profit calculation uses minSoFar, which only covers days before or equal to the current index. The temporal ordering of buy before sell is baked into the direction of iteration.

The Code

var maxProfit = function(prices) {
    let maxProfit = 0;
    let minSofar = prices[0];

    for (let i = 0; i < prices.length; i++) {
        if ((prices[i] - minSofar) > maxProfit) {
            maxProfit = prices[i] - minSofar;
        }
        if (prices[i] < minSofar) {
            minSofar = prices[i];
        }
    }
    return maxProfit;
};

We initialize maxProfit to 0, representing the baseline of making no trade. We initialize minSofar to prices[0], the only price we know at the start.

The for loop visits every element once. The first if checks whether selling today yields a better profit than anything seen so far. If prices[i] - minSofar beats maxProfit, we record the new best. The second if checks whether today's price is a new low. If it is, we update minSofar so future profit calculations use the best available buy price.

The ordering of the two conditions is deliberate. Profit is evaluated first, using the minimum from all previous days. Minimum is updated second. If we swapped the order, we could accidentally compute prices[i] - prices[i] on a day where the current price is a new low, which would yield a profit of 0 and potentially overwrite a valid positive maxProfit.

When the loop ends, maxProfit holds the best profit achievable with one transaction, and we return it.

Complexity Analysis

Common Mistakes

Mistake 1: Swapping the order of the two if conditions.

If you update minSofar before computing the profit, you can end up comparing a price to itself on a day where a new minimum appears. This yields a profit of 0 and can suppress a valid positive answer that was already stored in maxProfit.

// Wrong: minimum updated before profit is evaluated
if (prices[i] < minSofar) {
    minSofar = prices[i];
}
if ((prices[i] - minSofar) > maxProfit) { // now prices[i] - prices[i] = 0
    maxProfit = prices[i] - minSofar;
}

Always evaluate profit first, then update the minimum.

Mistake 2: Initializing minSofar to 0 instead of prices[0].

If you initialize minSofar = 0, then for any positive price, prices[i] - 0 = prices[i] looks like a valid profit. This is wrong because 0 is not a real price in the array. You can only buy at a price that actually appears, so minSofar must start at the first real price.

// Wrong: 0 is not a valid buy price
let minSofar = 0;

Mistake 3: Forgetting to return 0 when no profit is possible.

If you initialize maxProfit = prices[0] or some negative number, the function may return a negative value for a strictly decreasing input. The correct initialization is 0, which represents the option of not trading at all.

Mistake 4: Attempting to track the actual buy and sell days adds unnecessary complexity.

Some candidates try to record the indices where the optimal buy and sell occur. This is not required by the problem and introduces bugs where index updates happen out of sync with value updates. Only the profit value is needed.

Mistake 5: Using a nested loop to verify the greedy result.

After arriving at the one-pass solution, some candidates second-guess it and add a nested loop to "confirm" the answer. This undermines the entire point and brings the complexity back to O(n^2). Trust the greedy argument: the minimum so far is always the best buy candidate.

Interview Tips

Step 1: Name the brute force and its cost before proposing the optimization. Say: "The naive approach tries every buy-sell pair in O(n^2) time. For n = 10^5, that is too slow. I want to get this to O(n)."

Step 2: State the greedy observation explicitly. Say: "For any sell day, the best possible buy day is always the day with the lowest price before it. That means I do not need to re-scan the past on every step. I just need to remember the minimum."

Step 3: Name your two variables and their exact roles before writing a single line. Say: "minSoFar is the cheapest price I could have bought at up to today. maxProfit is the best profit I have seen so far. Both update in a single pass."

Step 4: Clarify the order of operations. Say: "I evaluate the profit before updating the minimum. This ensures I never accidentally compute the profit of buying and selling on the same day."

Step 5: Handle the edge case out loud. Say: "If prices only go down, every profit calculation is negative. Since maxProfit starts at 0 and we never update below 0, the function correctly returns 0, meaning we choose not to trade."

Key Takeaways

This is a state-tracking problem, not a trading problem. The domain is finance but the algorithm is pure array scanning. The moment you see it as "carry the best buy price forward," the solution writes itself.

One-pass solutions often hide behind a single remembered value. The move from O(n^2) to O(n) here did not require a new data structure. It required asking: "what single piece of information do I need to carry forward?" The answer was just the minimum so far.

Evaluate profit before updating the minimum. This ordering is not arbitrary. It is what correctly enforces the constraint that the sell day must come after the buy day. Getting this order wrong produces subtle bugs that can be hard to catch without a careful dry run.

Greedy decisions work when the locally best choice is always globally optimal. Here, always buying at the cheapest available price is provably optimal because there is no benefit to a more expensive buy under any future scenario. Recognizing when greedy is safe is one of the most valuable DSA skills to develop.

Closing

Day 8 is complete. A problem that looks like it requires exhaustive comparison turns out to need just two variables and a single scan. The O(n^2) brute force is never necessary once you accept that the best buy is always the cheapest price you have seen so far.

On Day 9, we keep building on this foundation. We will encounter another problem where a single scan and careful state management beats anything that involves re-scanning or nested loops.

If you found the ordering argument (profit before minimum) useful, or if you want to see how this pattern escalates with multiple transactions, drop a comment below. Every question helps me decide what to go deeper on in future posts.

See you on Day 9. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.