Best Time to Buy and Sell Stock — The One-Pass Insight Every FAANG Interviewer Tests

Problem Statement

Given 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 one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

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

Why 5? Buy on day 2 at price 1, sell on day 5 at price 6. Profit = 6 − 1 = 5. You cannot do better — selling at day 3 (price 5) only gives 4, and selling at day 6 (price 4) gives 3.

Example 2:

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

Why 0? Prices drop every single day. Every possible buy-sell pair produces a loss, so the best you can do is make no trade at all. Return 0, not a negative number.

Example 3:

Input:  prices = [2, 4, 1]
Output: 2

Why 2? Buy on day 1 at price 2, sell on day 2 at price 4. Profit = 4 − 2 = 2. Day 3 drops to 1, which is lower than both — but if you had waited to buy at 1, you have no future day to sell, so that opportunity is useless.

• Why This Problem Matters
• The "Aha" Moment
• Visual Dry Run
• Why the Wrong Approach Fails
• Common Mistakes
• Pattern Recognition
• Solutions
• Brute Force — O(n²) Time, O(1) Space
• Optimal Solution — O(n) Time, O(1) Space
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 121 is rated Easy, but do not let that fool you into skimming it. Amazon, Google, Microsoft, and Meta ask this problem — or its variants — specifically because it is a litmus test for how you think, not what you have memorized. Interviewers are watching to see whether you instinctively reach for brute force and then optimize, or whether you can reason about constraints (buy before sell) that eliminate naive approaches. The "running minimum" pattern this problem encodes is a foundational primitive that unlocks harder problems across arrays, dynamic programming, and sliding windows. Nail the mental model here, and you will recognize it in disguise on dozens of follow-ups.

The "Aha" Moment

Let's build the insight from scratch in plain English before touching any code.

You are walking through the price array from left to right — think of it as walking forward in time, day by day. On each day, you face a simple question: if I were to sell today, what is the maximum profit I could make?

To answer that, you need to know the cheapest price available before today. You already have that — you were there on every earlier day. As you walked forward, you can keep a mental note of the lowest price you have seen so far.

So the algorithm becomes two simple bookkeeping tasks done simultaneously in a single pass:

1. Track the minimum price seen so far. Every time you encounter a price lower than your current minimum, update it. This is your best possible buy price up to this moment.
2. Compute the profit if you sold today. Subtract the minimum price from today's price. If this profit beats the best profit recorded so far, update it.

That is the entire algorithm. No nested loops. No looking backward. One forward pass, two variables.

The key realization — the "aha" moment — is that you do not need to try every pair of (buy day, sell day). For any given sell day, the optimal buy day is always the cheapest day that occurred before it. And you can track that cheapest day on the fly as you scan forward.

Visual Dry Run

Let us trace through prices = [7, 1, 5, 3, 6, 4] step by step. We initialize min_price = infinity and max_profit = 0.

Walk through what happened:

• Day 0: Price is 7. min_price becomes 7. No profit yet.
• Day 1: Price drops to 1 — a new minimum. min_price becomes 1. Profit is 0 (you just found a cheaper buy point).
• Day 2: Price rises to 5. min_price stays 1. Profit = 5 − 1 = 4. New best.
• Day 3: Price is 3. min_price stays 1. Profit = 3 − 1 = 2. No improvement.
• Day 4: Price is 6. min_price stays 1. Profit = 6 − 1 = 5. New best.
• Day 5: Price drops to 4. min_price stays 1. Profit = 3. No improvement.

Final answer: 5. Achieved by buying on day 1 (price=1) and selling on day 4 (price=6).

Notice the order of operations matters in your implementation: always compute profit using the current min before updating the min. The table above applies min update first, but the arithmetic still works out because on any day where we update the min, the profit is zero (you cannot sell the same day you buy for a gain unless the price went up, which means it is not a new minimum). In code, both orderings produce the same result for this problem.

Why the Wrong Approach Fails

The most tempting wrong answer for this problem is:

"Just find the global minimum and the global maximum, and subtract them."

This fails immediately. Consider prices = [7, 1, 5, 3, 6, 4]. The global minimum is 1 (day 1). The global maximum is 7 (day 0). But day 0 comes before day 1 — you would be selling before you buy. That is not allowed.

Or consider prices = [3, 6, 1, 9]. Global min = 1 (day 2), global max = 9 (day 3). Profit = 8. That actually works here — but now try prices = [9, 1, 3, 6]. Global min = 1 (day 1), global max = 9 (day 0). You cannot sell at 9 after buying at 1 because 9 appears on day 0, before the buy at day 1.

The problem has a strict temporal ordering constraint: the buy day must come before the sell day. Finding extremes independently ignores this constraint entirely. Your algorithm must respect the direction of time, which is why the left-to-right scan with a running minimum is the correct mental model.

Common Mistakes

1. Using a brute-force nested loop and not optimizing. Many candidates write for i in range(n): for j in range(i+1, n): ... and call it done. That is O(n²) and will TLE on large inputs. Interviewers want to see you optimize, even if you mention brute force as a starting point. Always follow up: "can we do this in one pass?"

2. Returning a negative profit. The problem says return 0 if no profit is possible. Candidates sometimes initialize max_profit to a large negative number and forget to clamp the output, returning a negative value when the array is strictly decreasing. Always initialize max_profit = 0.

3. Updating min_price before computing today's profit (in some formulations). This is subtle. If you update min_price before checking price - min_price, and today's price is a new minimum, then price - min_price = 0, which is still correct — but the logic becomes harder to reason about. Make the order explicit in your code with a comment.

4. Confusing this problem with "max subarray" (Kadane's) without knowing why. Some candidates reach for Kadane's algorithm (converting the array to differences) but cannot explain why it works here. Interviewers will probe: "walk me through why that transformation is valid." If you use the Kadane approach, be ready to explain the connection — the difference array diff[i] = prices[i] - prices[i-1] transforms the problem into maximum subarray sum, which Kadane's solves. Understand it; do not just memorize it.

Pattern Recognition

This problem is a textbook example of the "running minimum/maximum" pattern: as you scan an array, you maintain a value (a running extreme) that represents the best state achievable up to the current index, and use it to compute the answer at each step in O(1) time.

This is also structurally equivalent to Kadane's algorithm for maximum subarray sum, just applied to profit rather than sum. If you convert prices into a daily-change array (diff[i] = prices[i] - prices[i-1]), the problem becomes: find the maximum sum contiguous subarray of diff. The running minimum approach and the Kadane approach are two faces of the same idea.

Recognizing this pattern is what separates candidates who merely solved this problem from candidates who have internalized a principle. When you see "optimize over a sequence where future decisions depend only on the best past state," think running min/max.

Solutions

Brute Force — O(n²) Time, O(1) Space

The starting point every interviewer expects you to mention. Try every possible buy-sell pair.

Python:

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        n = len(prices)

        # Try every pair (buy_day, sell_day) where sell_day > buy_day
        for buy in range(n):
            for sell in range(buy + 1, n):
                profit = prices[sell] - prices[buy]
                max_profit = max(max_profit, profit)

        return max_profit

JavaScript:

/**
 * Brute force: try every (buy, sell) pair where sell > buy.
 * Time: O(n^2) — will TLE on large inputs.
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
    let maxProfit = 0;
    const n = prices.length;

    for (let buy = 0; buy < n; buy++) {
        for (let sell = buy + 1; sell < n; sell++) {
            const profit = prices[sell] - prices[buy];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
    }

    return maxProfit;
}

Optimal Solution — O(n) Time, O(1) Space

Single pass. Track the minimum price seen so far and the best profit seen so far.

Python:

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # We cannot profit from an empty or single-day array
        if not prices:
            return 0

        min_price = float('inf')  # Cheapest buy price seen so far
        max_profit = 0            # Best profit seen so far (0 = no trade)

        for price in prices:
            if price < min_price:
                # Found a cheaper buy point — update our baseline
                min_price = price
            elif price - min_price > max_profit:
                # Today's sell profit beats the current best — update
                max_profit = price - min_price

        return max_profit

JavaScript:

/**
 * Optimal one-pass solution using running minimum.
 * For each day, ask: "if I sell today, what's my profit given the cheapest
 * price I've seen so far?" Track the best answer across all days.
 *
 * Time:  O(n) — single left-to-right scan
 * Space: O(1) — two scalar variables
 *
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
    let minPrice = Infinity;  // Cheapest buy price seen so far
    let maxProfit = 0;        // Best profit seen so far

    for (const price of prices) {
        if (price < minPrice) {
            // New cheapest day found — update our buy point
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            // Selling today beats our current best — record it
            maxProfit = price - minPrice;
        }
    }

    return maxProfit;
}

Complexity Analysis

Time complexity — optimal: We visit each element exactly once. Every operation inside the loop is O(1). Total: O(n).

Space complexity — optimal: We use two variables (min_price and max_profit) regardless of input size. No auxiliary arrays or hash maps. Total: O(1).

The brute force is quadratic because for each of n possible buy days, we scan up to n possible sell days. The optimal approach eliminates the inner loop by caching the relevant past information (the cheapest price so far) in a single variable.

Follow-up Questions

Interviewers almost never stop at LeetCode 121. The stock problem family is a ladder of increasing difficulty, and knowing where each rung sits shows you have internalized the pattern rather than memorized a solution.

LeetCode 122 — Best Time to Buy and Sell Stock II (Unlimited transactions) You can make as many transactions as you want. The key insight: every upward movement in price is profitable. Sum up all positive consecutive differences. profit = sum(max(0, prices[i] - prices[i-1]) for i in range(1, n)). Still O(n) time, O(1) space.

LeetCode 123 — Best Time to Buy and Sell Stock III (At most 2 transactions) Now you have a hard cap of two complete buy-sell cycles. You need to track four states as you scan: buy1, sell1, buy2, sell2. Each state feeds into the next. This is O(n) time, O(1) space but requires more careful state machine thinking. The key: process state transitions in reverse order (sell2 first) within each iteration to avoid using the same day twice.

LeetCode 188 — Best Time to Buy and Sell Stock IV (At most k transactions) Generalizes Problem 123 to k transactions. You need arrays of size k to store buy/sell states for each transaction count. If k ≥ n/2, it reduces back to Problem 122 (unlimited) because you can never make more than ⌊n/2⌋ transactions anyway. Time: O(n·k), Space: O(k). A crucial optimization most candidates miss.

LeetCode 309 — Best Time to Buy and Sell Stock with Cooldown (Unlimited + 1-day cooldown) After you sell, you must wait one day before buying again. This adds a state dependency across non-adjacent days: the earliest you can buy after selling on day i is day i+2. Solved with a three-state DP: held (holding stock), sold (just sold, in cooldown), rest (available to buy). O(n) time, O(1) space.

Summary of the ladder:

This Pattern Solves

The "running minimum/maximum" pattern from this problem reappears across many other interview questions:

• Maximum Subarray (LeetCode 53) — Kadane's algorithm maintains a running maximum ending at each index, analogous to the running minimum here.
• Trapping Rain Water (LeetCode 42) — For each bar, the trapped water depends on the maximum height seen to its left and right — two running extremes.
• Jump Game (LeetCode 55) — Track the farthest index reachable as you scan left to right (a running maximum of reach).
• Sliding Window Maximum (LeetCode 239) — Maintain the maximum within a window using a deque; shares the "track the optimal past state" idea.
• Product of Array Except Self (LeetCode 238) — Build prefix and suffix running products, then combine.

When you see an array problem that asks you to optimize something where the best future action depends on the best past state, the running min/max pattern should be your first instinct.

Key Takeaway

The core insight of LeetCode 121 is that you never need to revisit the past — you just need to carry a single number forward (the minimum price seen so far) and use it to evaluate each new day in O(1) time. This converts an O(n²) enumeration into an O(n) scan with constant space.

More importantly, this problem teaches a principle: when constraints impose an ordering (buy before sell), they often eliminate naive approaches and point directly toward the correct one. Recognizing which constraint eliminates which approach is the mark of a strong candidate — and that is exactly what FAANG interviewers are listening for.

Next: Problem 3 — Contains Duplicate →