Best Time to Buy and Sell Stock — One-Pass Greedy for FAANG

Problem Statement#

You are given an array prices where prices[i] is the price of a stock on day i. Pick a single day to buy and a later day to sell to maximize profit. Return zero if no profit is possible.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4
• Buy must occur before sell
• Only one transaction allowed

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

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

Why This Problem Matters#

Best Time to Buy and Sell Stock is the canonical greedy array interview question at Amazon, Google, and Microsoft. It tests whether you can spot that a problem with O(n^2) brute force can collapse to O(n) with one running aggregate.

The greedy single-pass mindset learned here generalizes to Maximum Subarray, Maximum Profit With Cooldown, and any problem where state at index i depends only on the best decision so far. Recruiters use this question to qualify candidates for the rest of the loop.

The Core Insight#

For every day j, the best profit ending on day j is prices[j] minus the minimum price seen before day j. Track both as you scan: a running minimum and a running maximum profit. One pass, O(1) space.

We do not need to remember the actual buy day. We only need the cheapest buy price seen so far, because any later sell day will compute against that minimum. This is the greedy invariant that converts O(n^2) into O(n).

The brute force is two nested loops checking every pair. The optimization comes from realizing that for a fixed sell day, only the historical minimum matters.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def maxProfit(self, prices):
        min_price = float('inf')
        best = 0
        for p in prices:
            if p < min_price:
                min_price = p
            else:
                best = max(best, p - min_price)
        return best

var maxProfit = function(prices) {
    let minPrice = Infinity;
    let best = 0;
    for (const p of prices) {
        if (p < minPrice) {
            minPrice = p;
        } else if (p - minPrice > best) {
            best = p - minPrice;
        }
    }
    return best;
};

Time: O(n) — single linear scan. Space: O(1) — two scalars.

Common Mistakes#

• Using a nested loop for O(n^2) when interviewer wanted optimal.
• Returning the negative profit when prices fall monotonically; clamp to zero.
• Updating min_price after computing profit, which would let you sell before you bought.
• Using max minus min globally, ignoring the order constraint.

Interview Tips#

• State the brute force first to anchor the conversation.
• Identify the bottleneck: scanning all earlier days for each sell day.
• Verbalize the invariant: min_price holds the cheapest buy seen so far.
• Confirm whether profit can be zero or must be strictly positive.

Follow-up Questions#

• What if you can do unlimited transactions? Hint: sum every positive delta.
• What if you can do at most two transactions? Hint: forward and backward pass.
• What if there is a cooldown after each sell? Hint: state machine DP.
• What if there is a transaction fee? Hint: subtract fee inside profit calc.
• What if k transactions are allowed? Hint: 2D DP with k as dimension.

Key Takeaways#

• LeetCode 121 reduces to tracking min_price and best_profit in one pass.
• Time O(n), space O(1) — the FAANG bar for this problem.
• Greedy works because for each sell day, only the historic minimum matters.
• This pattern is the warmup for Maximum Subarray and Kadane variants.
• Always clamp profit to zero; do not return negative values.
• Buy must precede sell — order constraint forces the running minimum.
• Variants with multiple transactions or cooldowns are common follow-ups.