122. Best Time to Buy and Sell Stock II
Asked at Meta, Apple, Oracle
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
3
Problem
You get an array prices, where prices[i] is the stock price on day i. You may buy and sell as many times as you want, but you can hold at most one share at any moment. So you must sell before you buy again.
Return the maximum total profit you can make. If no trade can earn money, return 0.
Because transactions are unlimited, every upward move is worth taking. If the price rises from day i to day i+1, you can buy on day i and sell on day i+1 and keep that gain. Adding up all such positive differences gives the best possible answer.
Pick the profitable up-moves
Constraints
- ●
1 <= prices.length <= 3 * 10^4 - ●
0 <= prices[i] <= 10^4
Examples
prices = [7,1,5,3,6,4]7prices = [1,2,3,4,5]4prices = [7,6,4,3,1]0Asked At
3 companies| 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.
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).
Sum every positive day-to-day change
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.