STEP 3 · ARRAYS · PREFIX MINIMUM · EASY

Best Time to Buy and Sell Stock

WHAT IT SAYS

Given daily prices, buy on one day and sell on a later day to make the largest possible profit (or none at all).

WHAT IT'S REALLY ASKING

"Stand on each day as if it were the selling day. The only thing about the entire past that can possibly matter to you is the single cheapest price you've already walked past — so why would you ever look at the past twice?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Check every buy-sell pair

O(n^2) time, O(1) space

For each day j, look back at every earlier day i and compute price[j] - price[i]. Keep the biggest difference you find, floored at zero.

WHERE THE WORK IS WASTED — The inner loop's only real job is to find the minimum price before day j — everything else it touches is irrelevant, because a non-minimum buy day is dominated by the minimum one. And it re-derives that minimum from scratch on every j, even though min(prices[0..j]) and min(prices[0..j-1]) differ by at most one new candidate. You scan i = 0 again on day 900 to learn a fact you already established on day 1.

KEY OBSERVATION — THE UNLOCKlink

The best buy for today was fixed before today began.

Fix the selling day j and ask what the past owes you. Profit is price[j] - price[i] with i < j. The term price[j] is a constant here — you cannot change it — so maximising profit means minimising price[i] over the days before j. Nothing else about those days survives the question: their order, their spread, their local peaks are all noise. The entire prefix compresses to one scalar, the running minimum. That is the whole reduction, and it flips the loop inside out. Instead of choosing a buy day and hunting for a sell day (which forces you to look forward, into the unknown), you choose the sell day and consult a fact about the past (which you already have). Forward-looking becomes backward-looking, and backward-looking is free — because you were standing there a moment ago. And the running minimum is maintainable in O(1): min(prices[0..j]) is just min(min so far, prices[j]). No rescan is ever necessary. A new low is not itself good news — it books no profit today — it is a cheaper option handed to every day that comes after it.

Carry the cheapest day with you

O(n) time, O(1) space, single pass

Walk left to right holding two numbers: the minimum price seen so far, and the best profit so far. At each day, first try selling — profit = today - minimum — and update the best; then update the minimum with today's price. Sell before you update, and the 'buy before you sell' rule enforces itself.

WHAT YOU TRADED — This buys speed with forgetfulness: you end up knowing the maximum profit but nothing about the second-best trade, and the single-transaction restriction is doing heavy lifting — allow k transactions and one scalar of history is no longer enough. The transferable move is fixing the right endpoint and asking 'what is the smallest summary of the prefix that answers this?' — the same reduction behind Kadane and prefix-sum tricks.

WATCH THE IDEA RUN

0cheapest

cheapest so far 7

best profit 0

Day 0 has no past to sell into. All it can do is become the past: it is the cheapest day so far, by default.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Fix the Right End, Compress the Left

YOU'LL SEE IT AGAIN WHEN

The answer is a function of two indices with an ordering constraint (i before j), and the objective separates so that only an extreme value of the prefix matters.
You catch yourself scanning backwards from every position to recompute a min, max, count or sum over a prefix that only grew by one element.
The statement is about a single transaction / single pair, not a combination — so the past can be summarised, not remembered.

SAME BLUEPRINT, DIFFERENT PROBLEM

Maximum Subarray (Kadane's Algorithm)Container With Most WaterTrapping Rain WaterBest Time to Buy and Sell Stock II

The bar isn't "solved it once." It's "could rebuild it from the observation."