Best Time to Buy and Sell Stock II
Asked at Meta, Apple, Oracle
Problem
Given an array of prices where prices[i] is the price of a stock on the ith day, maximize your profit by completing as many transactions as you like. You must sell the stock before buying again. This problem tests greedy reasoning about cumulative gains.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Apple | Medium | View all Apple questions → |
| Oracle | Medium | View all Oracle questions → |
How to Think About It
Greedy insight: whenever the price goes up from day i to day i+1, you capture that gain. Buy on day i, sell on day i+1. The total profit is the sum of all positive price differences. This works because you can hold only one share at a time.
Visual walkthrough for prices = [7,1,5,3,6,4]:
- 7 to 1: drop. No transaction. Profit = 0
- 1 to 5: gain of 4. Buy at 1, sell at 5. Profit = 4
- 5 to 3: drop. No transaction. Profit = 4
- 3 to 6: gain of 3. Buy at 3, sell at 6. Profit = 7
- 6 to 4: drop. No transaction. Profit = 7
Total: 4 + 3 = 7
Why greedy works here: you can make unlimited transactions. If prices go [1,5,10], buying at 1 and selling at 10 gives 9. But buying at 1, selling at 5 (gain 4), then buying at 5, selling at 10 (gain 5) also gives 9. The greedy approach of capturing every up-move is equivalent and simpler.
DP approach: dp[i][0] = max profit on day i holding no stock, dp[i][1] = max profit on day i holding stock. Transitions: dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]), dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]). Final answer: dp[n-1][0].
Complexity: greedy is O(n) time, O(1) space. DP is O(n) time, O(1) space (only need previous day). Both are equally efficient here.
Optimal Approach
Greedy: iterate through prices from index 1 to n-1. If prices[i] > prices[i-1], add the difference to total profit. This captures every profitable upswing.
Walkthrough with prices = [7,1,5,3,6,4]:
- i=1: 1 < 7. Skip.
- i=2: 5 > 1. Profit += 4. Total = 4.
- i=3: 3 < 5. Skip.
- i=4: 6 > 3. Profit += 3. Total = 7.
- i=5: 4 < 6. Skip.
- Result: 7
The key insight: buying at 1 and selling at 5, then buying at 3 and selling at 6 gives the same profit as buying at 1 and selling at 6, because you would have missed the dip at 3.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Confusing with Stock I where you can only make one transaction. In Stock II, you can make unlimited transactions. The greedy approach of summing all positive differences is specific to this unlimited-transaction variant.
Trying to find the single global minimum and maximum. That only works for one transaction. For multiple transactions, you need to capture every local upswing.
Overcomplicating with DP when greedy suffices. The DP solution is correct but unnecessary here. Mention both approaches and explain why greedy is simpler and equally efficient.
Forgetting that you must sell before buying again. You cannot hold multiple shares simultaneously. The greedy approach naturally handles this by buying and selling on consecutive days.
Not handling edge cases: all decreasing prices (profit = 0), single element array (profit = 0), all equal prices (profit = 0). These are valid inputs that should return 0.
Solution Code
def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profitFrequently Asked Questions
What is the Best Time to Buy and Sell Stock II problem?
Given an array of prices where prices[i] is the price of a stock on the ith day, maximize your profit by completing as many transactions as you like. You must sell the stock before buying again. This problem tests greedy reasoning about cumulative gains.
How do you solve Best Time to Buy and Sell Stock II?
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 II?
Best Time to Buy and Sell Stock II is asked at Meta, Apple, Oracle. It is a medium difficulty problem.
What are common mistakes on Best Time to Buy and Sell Stock II?
- Confusing with Stock I where you can only make one transaction. In Stock II, you can make unlimited transactions. The greedy approach of summing all positive differences is specific to this unlimited-transaction variant.
- Trying to find the single global minimum and maximum. That only works for one transaction. For multiple transactions, you need to capture every local upswing.
- Overcomplicating with DP when greedy suffices. The DP solution is correct but unnecessary here. Mention both approaches and explain why greedy is simpler and equally efficient.
- Forgetting that you must sell before buying again. You cannot hold multiple shares simultaneously. The greedy approach naturally handles this by buying and selling on consecutive days.
- Not handling edge cases: all decreasing prices (profit = 0), single element array (profit = 0), all equal prices (profit = 0). These are valid inputs that should return 0.