DSA Tracker

Visualize

Best Time to Buy and Sell Stock

One pass: track min price so far, bank the best profit

time O(n)space O(1)

You must buy BEFORE you sell, so the best sell at day i pairs with the cheapest price seen up to day i. One sweep keeps two numbers: minPrice (cheapest so far — the ideal buy day behind us) and best (largest sell-minus-min ever seen). Each day either lowers the buy floor or tries a sell against it — no nested loops needed.

Details

Animated on: Given daily prices [7, 1, 5, 3, 6, 4], pick one day to buy and one later day to sell for maximum profit.

Problem:Best Time to Buy and Sell StockEasy

One pass: track min price so far, bank the best profit

step 1 / 8

7
[0]
1
[1]
5
[2]
3
[3]
6
[4]
4
[5]

Day 0: price 7 is the only price seen, so minPrice = 7 and best = 0 (selling day 0 with no earlier buy earns nothing). min marks the cheapest buy day so far.

  • i=0· arr[0] = 7
  • min=0· arr[0] = 7
Pseudocode
1FUNCTION maxProfit(prices):
2  minPrice = prices[0]
3  best = 0
4  FOR i from 1 to (length of prices) - 1:
5    IF prices[i] < minPrice:
6      minPrice = prices[i]
7    ELSE:
8      best = the larger of best and (prices[i] - minPrice)
9  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Day 0: price 7 is the only price seen, so minPrice = 7 and best = 0 (selling day 0 with no earlier buy earns nothing). min marks the cheapest buy day so far.
  2. Day 1: price 1 < minPrice 7 — a cheaper buy day appeared. Selling today at 1 after buying at 7 would LOSE 6, so don't sell; lower the floor instead.
  3. minPrice = 1. Day 0's price 7 is discarded as a buy candidate forever: any future sell pairs better with 1 than with 7. best is still 0.
  4. Day 2: price 5 ≥ minPrice 1, so try selling: profit = 5 − 1 = 4. That beats best = 0 → best = 4 (buy day 1, sell day 2).
  5. Day 3: price 3 is neither a new low (3 > 1) nor a better sell: 3 − 1 = 2 < best 4. Nothing changes — the sweep just moves on.
  6. Day 4: price 6 against the floor of 1 gives profit = 6 − 1 = 5, beating best = 4 → best = 5. Buying the cheapest past day is what makes one comparison enough.
  7. Day 5: price 4. Not a new low (4 > 1), and selling yields 4 − 1 = 3 < best 5. The best trade so far — buy at 1, sell at 6 — survives.
  8. Scan done. Answer: max profit = 5 — buy on day 1 at price 1, sell on day 4 at price 6. One pass, two variables: O(n) time, O(1) space.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Best Time to Buy and Sell Stock in the editorAll Arrays problemsBack to roadmap