Buy and Sell Stock LeetCode 121 Deep Dive

LeetCode 121 — Best Time to Buy and Sell Stock — gives you an array prices where prices[i] is the price of a given stock on day i. You want to maximize your profit by choosing a single day to buy and a different day in the future to sell. If no profit is possible (prices are non-increasing), return 0. For example, given prices = [7, 1, 5, 3, 6, 4], the answer is 5: buy on day 2 (price = 1), sell on day 5 (price = 6). Given prices = [7, 6, 4, 3, 1], the answer is 0 because prices only decrease.

The problem imposes a strict chronological constraint: you must buy before you sell. This rules out simply finding the global minimum and global maximum and subtracting — the minimum might come after the maximum. The key challenge is efficiently finding the pair (buy_day, sell_day) with buy_day < sell_day that maximizes prices[sell_day] - prices[buy_day].

LeetCode 121 is rated Easy and appears in virtually every coding interview preparation list. It is the entry point to the Buy and Sell Stock series (LeetCode 122, 123, 188, 309, 714) which progressively adds constraints: multiple transactions, at most k transactions, cooldown periods, and transaction fees. Mastering the single-transaction greedy approach here is the foundation for all subsequent problems in the series.

The brute force approach checks every pair (i, j) where i < j and computes prices[j] - prices[i], tracking the maximum profit seen. Two nested loops give O(n^2) time complexity and O(1) space. For prices = [7, 1, 5, 3, 6, 4], the outer loop fixes buy day i, the inner loop scans every future sell day j, computes profit, and updates the maximum. This correctly finds the answer but runs in quadratic time.

For n up to 100,000 (the constraint on LeetCode 121), the brute force would perform up to 5 billion comparisons — far too slow. The O(n^2) approach is useful for verifying correctness of a faster solution on small inputs, but it is not acceptable as a final answer in an interview or on the OJ. The interviewer expects you to recognize that the quadratic scan is wasteful and propose a linear alternative.

The pivot to the optimal solution is this insight: when you are at sell day j, the best buy day is the minimum price in the range [0, j-1]. You do not need to re-scan [0, j-1] each time — you can maintain a running minimum as you iterate. This reduces the problem from O(n^2) to O(n) with a single extra variable.

The optimal solution uses a single pass with two variables: minPrice (initialized to infinity or prices[0]) and maxProfit (initialized to 0). For each price in the array, first update minPrice to be the minimum of minPrice and the current price, then update maxProfit to be the maximum of maxProfit and (current price minus minPrice). At the end, return maxProfit.

This works because at every sell day we are asking: "if I sold today, what is the best profit I could achieve?" The answer is current price minus the lowest price seen so far. By maintaining minPrice as we iterate, we answer this in O(1) per day. The maximum over all days gives the global best trade. There is no need to actually track which days correspond to the minimum and maximum — just the values.

The algorithm handles all edge cases gracefully. If prices only decrease (e.g., [7, 6, 4, 3, 1]), minPrice keeps dropping and profit is always negative or zero, so maxProfit stays at 0 — the correct answer. If there is only one price, no trade is possible and maxProfit is 0. If all prices are equal, profit is 0. Time complexity is O(n), space complexity is O(1).

There is an elegant mathematical equivalence between the buy-sell stock greedy and Kadane's algorithm on daily gains. Define the daily gain array as gains[i] = prices[i] - prices[i-1] for i from 1 to n-1. The profit from buying on day b and selling on day s equals prices[s] - prices[b] = gains[b+1] + gains[b+2] + ... + gains[s]. This is exactly the sum of a contiguous subarray of the gains array. Finding the maximum profit is therefore equivalent to finding the maximum subarray sum of the daily gains — the Maximum Subarray problem (LeetCode 53), solved by Kadane's algorithm.

Kadane's algorithm on the gains array processes each daily gain and decides: extend the current subarray or start a new one. If the running sum drops below 0, reset it to 0 (start fresh). Track the maximum running sum seen. The result is the maximum subarray sum of gains, which equals the maximum profit from buy/sell stock. Both the min-price approach and Kadane's on daily gains produce the same answer — they are mathematically equivalent reformulations of the same optimization.

Understanding both perspectives deepens your grasp of both problems. The min-price approach is more direct for LeetCode 121 and easier to explain in an interview. The Kadane connection is the key insight that links LeetCode 121 (Buy and Sell Stock) to LeetCode 53 (Maximum Subarray) — two problems that appear unrelated but share the same underlying structure. This connection frequently appears in follow-up interview questions.

The greedy choice is: at each day, if we were to sell today, the best buy is the historical minimum. This is locally optimal and globally optimal for the single-transaction problem. The argument for correctness is straightforward: the maximum profit over the entire array equals max over all sell days s of (prices[s] - min(prices[0..s-1])). The greedy algorithm computes exactly this by maintaining the running minimum.

We never need to look ahead because we are maximizing over all possible sell days in sequence. At each sell day s, we have already seen all possible buy days (indices 0 to s-1) and we know the minimum among them. The best we can do with a sell at day s is fully determined by the running minimum, which is available in O(1). There is no future information that could change the optimal buy for day s — if a cheaper buy day existed after s, it would not be a valid buy (must come before the sell).

The greedy approach fails for the multi-transaction variants (LeetCode 122 and beyond) only because those problems allow multiple buy-sell pairs that interact. For a single transaction, the greedy is provably optimal: the two-variable scan correctly finds the global optimum without any backtracking or dynamic programming table. This is one of the cleaner greedy proofs in the LeetCode canon.

Python solution: def maxProfit(prices): min_price = float('inf'); max_profit = 0; for price in prices: min_price = min(min_price, price); max_profit = max(max_profit, price - min_price); return max_profit. The loop processes each price once. float('inf') ensures the first price always updates min_price. If prices is empty (though the constraint guarantees length >= 1), max_profit returns 0 correctly. Time O(n), Space O(1).

Java solution: public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { minPrice = Math.min(minPrice, price); maxProfit = Math.max(maxProfit, price - minPrice); } return maxProfit; }. Integer.MAX_VALUE ensures the first price always becomes the initial minimum. The enhanced for-each loop is clean and idiomatic. Both solutions handle all-decreasing prices (maxProfit stays 0) and single-element arrays (loop runs once, profit = price - price = 0).

Common implementation mistakes to avoid: initializing minPrice to 0 instead of infinity or prices[0] — this causes incorrect results when all prices are positive (profit appears smaller than it is). Also avoid initializing maxProfit to a negative value — the problem guarantees return 0 if no profit is possible, so the floor should be 0. The two-variable pattern (minPrice, maxProfit) is the canonical O(n) O(1) solution and should be memorized for interviews.

Maximum Subarray (LeetCode 53) is mathematically equivalent to Buy and Sell Stock via the daily gains transformation. Both have O(n) time O(1) space solutions — Kadane's algorithm and the min-price scan respectively. House Robber (LeetCode 198) is another single-pass DP that processes each element once and maintains a small amount of state (the best profit with and without the previous house). Both problems reduce what looks like a 2D optimization to a 1D scan by exploiting the optimal substructure.

Climbing Stairs (LeetCode 70) and the Fibonacci family share the same "rolling two variables" pattern: you only need the last two values to compute the next one. Buy and Sell Stock uses two variables (minPrice, maxProfit) in the same spirit — no array or table needed, just two scalars updated in each iteration. This single-variable or two-variable rolling state is the hallmark of the greedy/DP O(1) space family.

For the multi-transaction variants: LeetCode 122 (unlimited transactions) uses a simple greedy of summing all positive daily gains. LeetCode 123 (at most 2 transactions) and LeetCode 188 (at most k transactions) require DP with transaction-count state. LeetCode 309 (with cooldown) and LeetCode 714 (with fee) add state-machine DP. The single-transaction greedy here is the cleanest case — understanding it deeply makes the harder variants accessible.