Best Time to Buy and Sell Stock
Maximize profit by choosing a single day to buy and a different day in the future to sell.
Problem Understanding
You are given an array prices where prices[i] is the price of a given stock on the i-th day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit. If no profit possible, return 0.
Strategy
We can iterate through the prices and keep track of:
- Min Price So Far: The lowest price we've seen to buy at.
- Max Profit: The best profit we could get if we sold today (
Current Price - Min Price).
Initialize
min_price = infinity,max_profit = 0.For each price
p:Update
min_price = min(min_price, p)Update
max_profit = max(max_profit, p - min_price)
Interactive Visualization
Initializing...
Watch how we track the minimum price seen so far to calculate maximum potential profit at each day.
Dry Run
prices = [7, 1, 5, 3, 6, 4]
| Day | Price | Min Price So Far | Potential Profit (Price - Min) | Max Profit |
|---|---|---|---|---|
| 1 | 7 | 7 | 7-7=0 | 0 |
| 2 | 1 | 1 | 1-1=0 | 0 |
| 3 | 5 | 1 | 5-1=4 | 4 |
| 4 | 3 | 1 | 3-1=2 | 4 |
| 5 | 6 | 1 | 6-1=5 | 5 |
| 6 | 4 | 1 | 4-1=3 | 5 |
Edge Cases & Common Mistakes
Watch out for these:
Prices Decreasing: If prices never go up (e.g., [7, 6, 4, 3, 1]), profit is 0. Don't return negative.
Empty Array: Return 0.
One Day: Cannot buy and sell. Return 0.
Complexity Analysis
- Time Complexity: O(N). We pass through the array once.
- Space Complexity: O(1). We use only two variables (
minPrice,maxProfit).
Solution
O(N) Time, O(1) Space.
1class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 min_price = float('inf')4 max_profit = 056 for price in prices:7 if price < min_price:8 min_price = price9 elif price - min_price > max_profit:10 max_profit = price - min_price1112 return max_profit
Complexity Analysis
- Time Complexity: O(N). Single pass.
- Space Complexity: O(1). Only two variables.