𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸
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:
- Set minPrice to Infinity.
- Set maxProfit to 0.
- Loop through each price.
- If the current price is lower than minPrice, update minPrice.
- 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