Challenge: best time to buy and sell
Find the maximum profit from one buy and one later sell — in a single pass.
- Spot when a nested-loop solution is hiding an O(n) one
- Solve a problem in a single pass by carrying a running value
Optional challenge. A bit of fun at the end of the track — puzzles where the obvious approach is too slow and a clever one isn't. These can't be brute-forced: the checks include an efficiency test that counts how many list reads your solution makes, so an O(n²) answer is rejected on any machine (no timing involved).
You're given a list of daily prices. Buy on one day, sell on a later day,
and maximise your profit. If no profit is possible, return 0.
The obvious solution compares every pair of days — buy at i, sell at every
j > i — which is O(n²). On a long price history that's hopeless. There's a way
to do it in a single pass.
Idea: walk left to right, remembering the lowest price seen so far. At each
day, the best profit if you sold today is today − cheapest_so_far. Track the
best of those. One loop, no pairs.
Write max_profit(prices): the largest profit from buying once and selling on a later day, or 0 if no profit is possible. Aim for O(n).
max_profit([7, 1, 5, 3, 6, 4]) → 5max_profit([7, 6, 4, 3, 1]) → 0If the efficiency check is red, you're still comparing pairs — collapse it to a single sweep that carries the cheapest-so-far.