ASAPUtils
The signal
“Buy before you sell” is an ordering constraint, and it’s the whole problem. It means that when
you’re standing on day i, everything in the future is irrelevant and almost everything in the
past is too. The one fact that matters is: what’s the cheapest I could have bought at?
Once you see that, the O(n²) double loop collapses to a single variable.
Approach ladder
1. Brute force — O(n²)
Try every buy day paired with every later sell day. Correct, times out at n ≤ 10⁵.
2. What is it wasting?
For each sell day it re-scans all the earlier days looking for the minimum — a minimum it already computed for the previous sell day. That running minimum can just be carried.
3. Optimal — one pass, O(1) space
Walk left to right holding minPrice. At each day, either it’s a new cheapest (update minPrice)
or it’s a selling opportunity (price - minPrice, compare against the best).
int maxProfit(vector<int>& p) {
int minPrice = INT_MAX, best = 0;
for (int x : p) {
if (x < minPrice) minPrice = x;
else best = max(best, x - minPrice);
}
return best;
}
function maxProfit(p) {
let minPrice = Infinity, best = 0;
for (const x of p) {
if (x < minPrice) minPrice = x;
else best = Math.max(best, x - minPrice);
}
return best;
}
Why this counts as a sliding window
It’s the degenerate case: the window is [buyDay, today], and its left edge only ever jumps
forward to a new cheapest day. There’s no shrink loop because there’s nothing to invalidate — but
the shape (one pointer advancing, state carried, answer recorded each step) is the same one you’ll
use for the rest of week 2. Starting here makes the harder windows feel familiar.
Walkthrough
[7, 1, 5, 3, 6, 4]:
| day | price | minPrice | profit if sold | best |
|---|---|---|---|---|
| 0 | 7 | 7 | — | 0 |
| 1 | 1 | 1 | — | 0 |
| 2 | 5 | 1 | 4 | 4 |
| 3 | 3 | 1 | 2 | 4 |
| 4 | 6 | 1 | 5 | 5 |
| 5 | 4 | 1 | 3 | 5 |
Complexity
- Time O(n) — one pass.
- Space O(1) — two variables.
Traps
- Initialising
bestto a negative number. Doing nothing is always allowed, so the floor is 0. - Allowing a sell before the buy. The
elsebranch matters: if today set a new minimum, you can’t also sell today at a profit. - Confusing this with Best Time to Buy and Sell Stock II, where unlimited transactions are allowed and the answer is the sum of every upward step. Read which variant you’re on.
Blank re-solve prompt
Given daily prices, return the maximum profit from a single buy followed by a later sell. One pass, O(1) space.