~20 minutes · Day 1 · greedy min-tracking · Python
Tonight's problem is Best Time to Buy and Sell Stock. It is an interview classic because it looks like finance, but the useful skill is simpler: while scanning once, carry the best fact from the past so today is easy to judge.
Best sell = today's price minus the cheapest price seen so far; one pass, carry the min.
That's the whole pattern. For each day, pretend today is the sell day. The only buy day worth considering is the cheapest earlier price. If you carry that one number, you never need to look backward again.
The scan only needs the cheapest earlier price, then today's profit is one subtraction.
The LeetCode statement gives one price per day and asks for the best profit from one buy before one sell. The obvious brute force is O(n²): try every earlier buy with every later sell.
def max_profit(prices):
best = 0
for buy in range(len(prices)):
for sell in range(buy + 1, len(prices)): # every valid later sale
best = max(best, prices[sell] - prices[buy])
return best
This works, but the inner loop keeps asking the same kind of question: “what was the cheapest buy before this sell?” A greedy algorithm keeps the locally best choice needed for the next step (Wikipedia: greedy algorithm). Here, that choice is the cheapest price so far.
Walk left to right. At each price, first test the profit from selling today. Then update the cheapest price for future days. Python's max and min keep the two carried values small and explicit.
def max_profit(prices):
cheapest = prices[0] # cheapest buy seen so far
best = 0 # best profit seen so far
for price in prices[1:]:
best = max(best, price - cheapest) # sell today?
cheapest = min(cheapest, price) # new future buy?
return best
The order matters for the story: today's sell uses the cheapest price from the past. After that, today can become the cheapest price for a later sell.
Check profit before updating the carried minimum, so the buy day stays earlier than the sell day.
Suppose you get daily temperatures and need the biggest rise from an earlier day to a later day. Before opening the answer: what single value should the loop carry?
def biggest_rise(temps):
coldest = temps[0]
best = 0
for temp in temps[1:]:
best = max(best, temp - coldest) # rise if today ends it
coldest = min(coldest, temp) # carry the best start
return best
Same invariant: best ending today = today's value minus the smallest earlier value. Only the nouns changed.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every buy and sell) | O(n²) | O(1) |
| Greedy min-tracking (carry cheapest so far) | O(n) | O(1) |
The win is not a new data structure. It is the discipline to carry exactly the past fact the future needs.
1. What value must the loop carry for this pattern?
price - cheapest.2. Spot the bug in this loop:
cheapest = prices[0]
best = 0
for price in prices[1:]:
best = max(best, price - cheapest)
cheapest = max(cheapest, price)cheapest, but the code uses max. That carries the highest price so far, which makes later profits too small or negative.3. Which problem has the same min-tracking shape?
4. Why is the brute force version slow?
Solve Best Time to Buy and Sell Stock in your Notion tracker with the cycle — predict → attempt → compare → encode:
Watch NeetCode — Best Time to Buy and Sell Stock at the compare step. Listen for how he decides what value the loop must remember.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.