Pick one day to buy and a later day to sell so the profit is as large as possible; return 0 when no profitable trade exists.
Before you code
Pairing every buy with every later sell is quadratic. The order of days does the work for you: for each sell day, the best partner is the cheapest day before it, so tracking that cheapest day as you go is enough.
Hints
- Scan left to right holding the lowest price seen so far.
- Treat each day as a possible sell day:
profit_today = price - lowest_before, and remember the best value seen. - Never let a day buy and sell to itself — compare first, then update the lowest price — and never return a negative number when prices only fall.
Production & complexity notes
When solving Best Time to Buy and Sell Stock on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Cache-Conscious Data Structures: Alignment, False Sharing, and Structure of Arrays to reinforce the underlying pattern.
What it practices
One running aggregate over each prefix instead of re-scanning the past, from Prefix sums.