Sliding window

Episode 15 Best Time to Buy and Sell Stock

5 min · LeetCode 121 · Java

Title card of Episode 15: Best Time to Buy and Sell Stock

▶ This video is coming to YouTube soon.

LeetCode 121, Best Time to Buy and Sell Stock, solved on screen. Three examples show the rules: you can't sell before you buy, a falling price means no trade (0), and the cheapest day isn't always the day to buy. Then we watch the brute force try every buy and sell day, read its code line by line, and see why it's O(n²). Finally, one pass keeps buy on the cheapest day so far and sells today: the window from Episode 13, in O(n) time and O(1) space.

What you'll learn

  • What Best Time to Buy and Sell Stock asks, through three worked examples
  • The brute force: every buy and later sell day, O(n²) time, O(1) space
  • The key idea: the best buy for today is the cheapest day before it
  • The one-pass window: O(n) time, O(1) space
  • Why moving buy to a cheaper day never loses the answer

Chapters

  1. 0:00The problem
  2. 0:16Examples
  3. 0:58Brute force, visualized
  4. 1:47Brute force: the code
  5. 2:01Brute force, line by line
  6. 2:36One pass: the idea
  7. 2:58One pass, visualized
  8. 3:49One pass: the code
  9. 4:03One pass, line by line
  10. 4:49Comparing the approaches