visual walkthrough
Best Time to Buy and Sell Stock
Track the best buy so far; the gentlest window-style problem and extremely common.
The idea
To sell on a given day, the best day to have bought is the cheapest day before it. So walk forward, always remembering the lowest price so far, and check what selling today would earn.
No need to compare every pair: the lowest-so-far already is the best partner for every later day.
Complexity
| approach | time | space |
|---|---|---|
| Every buy and sell pair | O(n²) | O(1) |
| Track the lowest so far | O(n) | O(1) |