Best Time to Buy and Sell Stock
Asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Adobe, Atlassian, Salesforce, Walmart
Problem
You are given an array where each element represents the price of a stock on a given day. Find the maximum profit you can achieve by buying once and selling once. This is a classic problem that tests whether you can think about optimal substructure.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Apple | Easy | View all Apple questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Oracle | Easy | View all Oracle questions → |
| Adobe | Easy | View all Adobe questions → |
| Atlassian | Easy | View all Atlassian questions → |
| Salesforce | Easy | View all Salesforce questions → |
| Walmart | Easy | View all Walmart questions → |
How to Think About It
Brute force: try every possible buy day i and sell day j where j > i. Calculate profit = prices[j] - prices[i]. Track the maximum. That's O(n²) — too slow for large arrays.
Key insight: you don't need to track the buy day. Just track the minimum price seen so far. At each day, the best profit you can make by selling today is (today's price - minimum seen so far).
Why this works: if you know the minimum price up to today, selling today gives the maximum possible profit for that buy point. You don't care where the minimum was — you just need the value.
The invariant: min_price is always the cheapest price from day 0 to today. max_profit is always the best profit achievable from day 0 to today. Both update as you walk through the array.
Visual walkthrough for [7,1,5,3,6,4]:
Day: 0 1 2 3 4 5
Price: 7 1 5 3 6 4
- Day 0: min=7, profit=0, max=0
- Day 1: min=1, profit=0, max=0
- Day 2: min=1, profit=5-1=4, max=4
- Day 3: min=1, profit=3-1=2, max=4
- Day 4: min=1, profit=6-1=5, max=5
- Day 5: min=1, profit=4-1=3, max=5
Result: 5 (buy day 1, sell day 4)
Edge cases: prices always decreasing (never profitable — return 0), single price (can't sell — return 0), all same prices (no profit — return 0).
Optimal Approach
Initialize min_price = infinity and max_profit = 0. Iterate through prices:
- Update min_price = min(min_price, current price)
- Calculate profit = current price - min_price
- Update max_profit = max(max_profit, profit)
The key realization: you never need to know which day you bought on. You just need the minimum price up to today. By the time you sell, the buy decision is already made — you picked the cheapest day.
Time: O(n) — single pass. Space: O(1) — just two variables.
What Trips People Up in Real Interviews
Confusing "buy low, sell high" with "find the maximum difference." The sell must come after the buy — you can't sell before buying. This constraint makes it different from max subarray.
Trying to find the global minimum and global maximum. That doesn't work if the max comes before the min. You need to track the running minimum as you iterate from left to right.
Forgetting that you must buy before you sell. If all prices are decreasing, the answer is 0 (no profit), not the difference between the highest and lowest prices.
Not handling the edge case of a single price (return 0) or two prices where the second is lower (return 0).
Updating min_price only when max_profit improves. You must update min_price at every step independently — the cheapest day might appear well before the best selling opportunity, and skipping updates breaks the invariant.
Solution Code
def maxProfit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profitFrequently Asked Questions
What is the Best Time to Buy and Sell Stock problem?
You are given an array where each element represents the price of a stock on a given day. Find the maximum profit you can achieve by buying once and selling once. This is a classic problem that tests whether you can think about optimal substructure.
How do you solve Best Time to Buy and Sell Stock?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Best Time to Buy and Sell Stock?
Best Time to Buy and Sell Stock is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Adobe, Atlassian, Salesforce, Walmart. It is a easy difficulty problem.
What are common mistakes on Best Time to Buy and Sell Stock?
- Confusing "buy low, sell high" with "find the maximum difference." The sell must come after the buy — you can't sell before buying. This constraint makes it different from max subarray.
- Trying to find the global minimum and global maximum. That doesn't work if the max comes before the min. You need to track the running minimum as you iterate from left to right.
- Forgetting that you must buy before you sell. If all prices are decreasing, the answer is 0 (no profit), not the difference between the highest and lowest prices.
- Not handling the edge case of a single price (return 0) or two prices where the second is lower (return 0).
- Updating min_price only when max_profit improves. You must update min_price at every step independently — the cheapest day might appear well before the best selling opportunity, and skipping updates breaks the invariant.