Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day. Maximize your profit by choosing a single day to buy and a different day to sell.
Examples
prices = [7,1,5,3,6,4]
5
Buy on day 2 (price=1) and sell on day 5 (price=6), profit = 5.
prices = [7,6,4,3,1]
0
No transactions are done and the max profit is 0.
Constraints
- •
1 <= prices.length <= 10^5 - •
0 <= prices[i] <= 10^4
Approaches
Check all possible pairs of buy and sell days.
def max_profit(prices):
max_profit = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
profit = prices[j] - prices[i]
max_profit = max(max_profit, profit)
return max_profitKeep track of the minimum price seen so far and compute max profit at each step.
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profitTrack minimum and compute max profit in one pass.
Diagram
def max_profit(prices):
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profitComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check all possible pairs of buy and sell days. |
| Track Minimum Price | O(n) | O(1) | Keep track of the minimum price seen so far and compute max profit at each step. |
| Single Pass | O(n) | O(1) | Track minimum and compute max profit in one pass. |
Check all possible pairs of buy and sell days.
Keep track of the minimum price seen so far and compute max profit at each step.
Track minimum and compute max profit in one pass.
Common Mistakes
Trying to find the global minimum and maximum instead of a valid buy-sell pair
Not handling the case where prices only decrease
Using a two-pass approach when one pass suffices