Best Time to Buy and Sell Stock: tracking the running minimum

prices = [7,1,5,3,6,4] — the answer is 5. Buy at index 1, sell at index 4. That gap, from 1 to 6, is the widest profitable spread in the array. The problem is finding it without checking every pair.

What the constraints force

The array can be up to 10⁵ elements long. That single constraint kills the brute-force approach before you write a line — 10⁵ squared is 10¹⁰ operations, which no online judge will sit through. Prices range from 0 to 10⁴, so they fit comfortably in an int and there is no overflow to worry about. The minimum array length is 1, which means no transaction is always a valid outcome: if there is only one price, you cannot sell, so the function should return 0.

Those two facts together — "must be linear" and "return 0 if no profit is possible" — define the shape of the solution before any algorithm design happens.

Brute force: try every pair

The most literal reading of the problem: for every possible buy day i, check every possible sell day j > i and keep the best profit.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        max_profit = 0
        n = len(prices)
        for i in range(n - 1):
            for j in range(i + 1, n):
                max_profit = max(max_profit, prices[j] - prices[i])
        return max_profit

public class Solution {
    public int MaxProfit(int[] prices) {
        int maxProfit = 0;
        int n = prices.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                maxProfit = Math.Max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
}

O(n²) time, O(1) space. Correct on every input. Still a timeout with n = 10⁵.

Walk through [7,1,5,3,6,4] to see what is happening. When i = 0 (buy at 7), every sell candidate is lower except 5, and even that gives 5 - 7 = -2. No gain. When i = 1 (buy at 1), the inner loop computes 5-1=4, 3-1=2, 6-1=5, 4-1=3. The best here is 5. No later buy day beats it. Answer: 5.

The redundancy is visible: for each sell day j, the inner loop searches backward through every prior day to find the cheapest buy. But once you have scanned days 0 through j-1, you already know the minimum price in that range. You just need to carry it forward.

The O(n) solution: sliding window / running minimum

The insight fits in one sentence: to maximize profit when selling on day j, buy on the cheapest day before j. You do not need to search for that cheapest day each time — you maintain it as a running minimum while scanning left to right.

The sliding-window framing makes this concrete. Left pointer L is the buy day; right pointer R is the sell day. Both start at index 0 and R begins scanning from index 1. At each step:

• If prices[R] < prices[L], the right pointer found a cheaper entry point. Move L to R — the old buy day is now irrelevant.
• Otherwise, prices[R] - prices[L] is a candidate profit. Update the running maximum.
• Always advance R.

Neither pointer ever moves backward. Each element is visited exactly once. That is why the algorithm is O(n).

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        left, right = 0, 1
        max_profit = 0
 
        while right < len(prices):
            if prices[right] < prices[left]:
                left = right
            else:
                max_profit = max(max_profit, prices[right] - prices[left])
            right += 1
 
        return max_profit

public class Solution {
    public int MaxProfit(int[] prices) {
        int left = 0, right = 1;
        int maxProfit = 0;
 
        while (right < prices.Length) {
            if (prices[right] < prices[left]) {
                left = right;
            } else {
                maxProfit = Math.Max(maxProfit, prices[right] - prices[left]);
            }
            right++;
        }
 
        return maxProfit;
    }
}

Step through [7,1,5,3,6,4] by hand:

L lands on index 1 immediately and never moves again — price 1 is the global minimum and every subsequent day is more expensive. The maximum spread is captured at step 4.

Now step through example 2, [7,6,4,3,1]:

Prices fall every day. L chases R across the entire array; the else branch is never entered. max_profit stays at 0 — no transaction is profitable, so don't trade.

The running minimum form

You will also see this written without explicit pointer names:

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        max_profit = 0
        for price in prices[1:]:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)
        return max_profit

public class Solution {
    public int MaxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.Length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxProfit = Math.Max(maxProfit, prices[i] - minPrice);
            }
        }
        return maxProfit;
    }
}

Mechanically identical to the pointer version. min_price is the left pointer's position; the for loop is the right pointer advancing. The computation is the same; only the framing differs. I reach for the explicit pointer form when explaining the problem because it makes the window structure visible, but either version is fine to submit. I'd actually ship the running minimum version in a real interview because it reads closer to the natural language of the problem.

The DP connection

There is a dynamic programming reading of this that is worth having in your back pocket for interviews. Define:

dp[i] = maximum profit achievable if we sell on day i

Then:

dp[i] = prices[i] - min(prices[0], prices[1], ..., prices[i-1])

The answer is max(dp[0], dp[1], ..., dp[n-1]). Notice that computing each dp[i] only needs the running minimum of everything before it — you do not need the full dp array. That is the O(1) space collapse: the variable min_price in the loop above is exactly that running minimum, and max_profit accumulates the max over all dp[i]. The single-pass algorithm is the space-optimised DP, and recognising that connection matters in interviews where you might be asked to "show the DP" first.

Complexity

Both approaches use O(1) extra space — the brute force only needs loop counters, and the optimal only needs two variables. The time gap is the only thing that matters here, and it is decisive.

Edge cases

• Single-element array, e.g. [5]: The while loop starts with right = 1 and len = 1, so right < len is false immediately. Returns 0 without entering the loop — no special case needed.
• Strictly decreasing array, e.g. [7,6,4,3,1]: Every step moves L forward because each new price is cheaper. The else branch is never reached. Returns 0 — correct, because no transaction yields a positive return.
• All prices equal, e.g. [3,3,3,3]: Each prices[R] - prices[L] is 0, so max_profit stays 0. Returns 0.
• Strictly increasing array, e.g. [1,2,3,4,5]: L never moves from index 0 because no later price is cheaper than 1. The profit grows with each step and peaks at 5 - 1 = 4 on the last day.
• Peak in the middle, e.g. [1,9,1,9]: The algorithm correctly finds profit 8 (buy at index 0, sell at index 1 or buy at index 2, sell at index 3 both give 8). After L resets to index 2, the second window [1,9] also gives 8. The answer is 8.

Pattern: order-constrained pair optimisation

The shape of problem that should trigger this solution: find a pair (arr[i], arr[j]) with i < j that maximises some function of the two values. The technique is always the same — scan left to right, maintain a running extreme on the left side, evaluate the right side at each position. The running minimum is not a trick specific to stock prices; it is a general technique for any order-constrained pair problem.

Keywords that point here: "buy and sell," "single transaction," "maximum difference with order constraint," "you must buy before you sell."

Where this fits in the series

This is the first problem in the sliding-window series because it has the cleanest window possible: no size constraint, no character map, no shrink condition — just a left pointer that jumps forward when a new minimum is found. Everything else in the series adds one layer of complexity on top of this skeleton.

• Longest Substring Without Repeating Characters (3): the window still has L and R, but now L must shrink whenever a duplicate character enters from the right. A hash map tracks character positions. The validity condition replaces the "found a cheaper entry" condition.
• Longest Repeating Character Replacement (424): you are allowed to replace up to k characters in the window. When to move L depends on window_size - max_frequency > k.
• Minimum Window Substring (76): instead of maximising, you minimise the window length subject to a coverage constraint. L only moves when the window is already valid — the opposite of this problem's pointer movement direction.

Solve 121 first not because of the difficulty rating but because the mechanics are pure. Once you see L and R moving across a price array with a clean invariant, the additions in the problems above are easier to reason about.