Best Time to Buy and Sell Stock — One-Pass Min Tracker

Beginner 8 min read

What you'll learn

✓Brute-force approach and its complexity
✓Optimal approach with intuition
✓Edge cases that trip people up
✓How to talk through it in an interview
✓Related problems to follow up with

Prerequisites

•Basics from arrays introduction and Big O notation

Best Time to Buy and Sell Stock looks like a trick question the first time you see it, then becomes a one-liner once you see the pattern. The lesson it teaches, tracking a running extreme while sweeping the array, comes up constantly.

The Problem

You are given an array prices where prices[i] is the price of a stock on day i. You want to maximize profit by choosing a single day to buy and a different later day to sell. Return the maximum profit; if no profit is possible, return 0.

Example:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price 1) and sell on day 5 (price 6).

Buying after selling is not allowed, which is the only real constraint.

Intuition

The brute force tries every pair where the buy day comes before the sell day. That is O(n^2) and times out on large inputs.

The key insight: at each day i, the best sell price is just prices[i], and the best profit you could achieve by selling today is prices[i] - min(prices[0..i-1]). So we only need to track the minimum price seen so far. As we sweep the array left to right, we keep a running minimum and a running best profit. One pass, two scalars.

Explanation with Example

Walk through prices = [7, 1, 5, 3, 6, 4].

Start: min_price = 7, best = 0.
Day 1, price 1. Profit if sell = 1 - 7 = -6. best stays 0. Update min_price to 1.
Day 2, price 5. Profit = 5 - 1 = 4. best becomes 4. min_price stays 1.
Day 3, price 3. Profit = 3 - 1 = 2. best stays 4.
Day 4, price 6. Profit = 6 - 1 = 5. best becomes 5.
Day 5, price 4. Profit = 4 - 1 = 3. best stays 5.

Return 5. Order matters: compute the candidate profit before updating min_price, otherwise you would be selling and buying on the same day.

day     0   1   2   3   4   5
price   7   1   5   3   6   4
min     7   1   1   1   1   1
profit  0   0   4   2   5   3
                      ^
                      best = 5

Running min sweep across prices

Code

def max_profit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    best = 0
    for price in prices[1:]:
        best = max(best, price - min_price)
        min_price = min(min_price, price)
    return best

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int minPrice = prices[0];
        int best = 0;
        for (int i = 1; i < prices.length; i++) {
            best = Math.max(best, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return best;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int minPrice = prices[0];
        int best = 0;
        for (size_t i = 1; i < prices.size(); ++i) {
            best = max(best, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        return best;
    }
};

Edge Cases

Strictly decreasing prices like [7, 6, 4, 3, 1]. No profitable trade exists. Return 0.
Single-element array. No trade possible. Return 0.
Empty array. Defensive check at the top.
All equal prices. Profit is 0.
Integer overflow. Not a Python concern, but in C++ or Java you should think about it.

Complexity Analysis

Time: O(n). One pass.
Space: O(1). Two scalars regardless of input size.

This is as efficient as the problem allows; you must look at every price at least once.

How to Explain It in an Interview

Restate the problem and confirm: you can only buy once and sell once, and sell day must come after buy day.
Mention the brute force in one sentence to anchor complexity.
Explain the key insight: “For each day, I only care about the minimum I have seen so far. The best profit ending at this day is price minus running min.”
Code it and emphasize the order: compute profit first, then update min.
State O(n) time and O(1) space.
Mention the multi-transaction variant if asked for an extension.

For the array fundamentals that make this trivial, see arrays common operations.

Wrap up

The pattern here, “sweep once, maintain a running extreme, derive the answer at each step”, is one of the most reusable ideas in array problems. Maximum Subarray uses the same skeleton with a running sum instead of a running min. Master it on this problem and a dozen others fall out for free.