𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸

Leetcode 121 asks you to find the best time to buy and sell a stock. You get an array of prices. Each index is a day. The value is the cost on that day.

The goal is simple. Buy on one day and sell on a future day to get the most profit. If no profit is possible, return 0.

The Problem Constraints:

  • Array length up to 100,000.
  • Prices up to 10,000.
  • You must sell after you buy.

Approach 1: The Naive Method (Brute Force)

The brute force way checks every single buy and sell pair. This uses two loops.

  • Time Complexity: O(n²)
  • Problem: It is too slow.

If you have 1,000 days, you perform 1,000,000 checks. If you have 100,000 days, you perform 10,000,000,000 checks. This causes a timeout on Leetcode.

Approach 2: The Optimized Method (One Pass)

You can solve this in one pass using two variables: minPrice and maxProfit.

  • Time Complexity: O(n)
  • Space Complexity: O(1)

How it works:

  1. Set minPrice to Infinity.
  2. Set maxProfit to 0.
  3. Loop through each price.
  4. If the current price is lower than minPrice, update minPrice.
  5. If the current price minus minPrice is greater than maxProfit, update maxProfit.

Example trace with prices [7, 1, 5, 3, 6, 4]:

  • Day 1: Price 7. minPrice becomes 7. maxProfit stays 0.
  • Day 2: Price 1. minPrice becomes 1. maxProfit stays 0.
  • Day 3: Price 5. 5 - 1 = 4. maxProfit becomes 4.
  • Day 4: Price 3. 3 - 1 = 2. maxProfit stays 4.
  • Day 5: Price 6. 6 - 1 = 5. maxProfit becomes 5.
  • Day 6: Price 4. 4 - 1 = 3. maxProfit stays 5.

Final Answer: 5.

The optimized version wins because it only looks at each price once. It scales well for large datasets.

Source: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1