Best Time to Buy and Sell Stock

EasyArrays · Running Minimum🧩 Array Manipulation LeetCode #121 ↗Updated Oct 30, 2026

Problem

You get prices, where prices[i] is a stock's price on day i. You may make one trade: buy on some day and sell on a strictly later day. Return the largest profit you can lock in, or 0 if every possible trade loses money.

Inputprices = [7,1,5,3,6,4]Output5 (buy at 1, sell at 6)

Inputprices = [7,6,4,3,1]Output0 (prices only fall)

1 ≤ n ≤ 10⁵ · 0 ≤ prices[i] ≤ 10⁴

Try it yourself

Java

class Solution {
    public int maxProfit(int[] prices) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

For any sell day, the best buy day is simply the cheapest day seen so far. Carry that minimum forward and each day becomes a single subtraction.

PatternArray Manipulation

Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.

Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.

Open the Array Manipulation guide →

Approaches

Brute ForceTry Every Buy/Sell Pair

Time O(n²)Space O(1)

Fix a buy day i, then try every later sell day j and keep the best prices[j] - prices[i]. Starting the answer at 0 covers the “don't trade” option.

Java

public int maxProfit(int[] prices) {
    int best = 0;
    for (int buy = 0; buy < prices.length; buy++) {
        for (int sell = buy + 1; sell < prices.length; sell++) {
            best = Math.max(best, prices[sell] - prices[buy]);
        }
    }
    return best;
}

Obviously correct, but ~5·10⁹ pair checks at n = 10⁵ times out.

BetterSuffix Maximum Array

Time O(n)Space O(n)

Precompute maxAfter[i] = highest price on day i or later (one right-to-left pass). Buying on day i then earns at most maxAfter[i] - prices[i], so one more pass finds the answer.

Java

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] maxAfter = new int[n]; // max price from day i to the end
    maxAfter[n - 1] = prices[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        maxAfter[i] = Math.max(prices[i], maxAfter[i + 1]);
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        best = Math.max(best, maxAfter[i] - prices[i]);
    }
    return best;
}

Linear time, but the helper array costs O(n) memory.

OptimalOne Pass — Track the Cheapest Day

Time O(n)Space O(1)

Flip the view: treat each day as the sell day. The best buy for it is the lowest price before it, which we keep in minPrice. Update the profit first, then the minimum, so we never sell before we buy.

Java

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE; // cheapest price seen so far
    int best = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;               // better day to buy
        } else {
            best = Math.max(best, price - minPrice); // sell today?
        }
    }
    return best;
}

Dry runprices = [7,1,5,3,6,4]

m minPrice dayd today changed

d=0
7
d m
1

5

3

6

4

min=7, best=0
d=1
7

1
d m
5

3

6

4

new min=1
d=2
7

1
m
5
d
3

6

4

5-1=4 → best=4
d=3
7

1
m
5

3
d
6

4

3-1=2, keep 4
d=4
7

1
m
5

3

6
d
4

6-1=5 → best=5
d=5
7

1
m
5

3

6

4
d
4-1=3 → 5 ✔

Single pass, two variables — the expected interview answer.

Pro tip

This is Kadane in disguise: it is the max subarray sum of the day-to-day price differences.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Buy/Sell Pair	`O(n²)`	`O(1)`
Better	Suffix Maximum Array	`O(n)`	`O(n)`
Optimal	One Pass — Track the Cheapest Day	`O(n)`	`O(1)`

Common pitfalls

Taking max - min of the whole array — the minimum may come after the maximum.
Returning a negative number when prices only fall — the answer floors at 0.
Pairing a price with a minimum taken from a later day — that sells before buying.

Interview tips

Say the brute force in one line, then ask: “for a fixed sell day, which buy day wins?”
Name the invariant: minPrice = cheapest price strictly before or on today.
Mention the Kadane link — it sets up the multi-transaction follow-ups nicely.

Pattern

Running min/max (prefix state) → best pair (i < j) where the score depends on one earlier and one later element.

My notes saved in this browser