Watch 10 video solutions for Best Time to Buy and Sell Stock II, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by NeetCode has 142,874 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104Problem Overview: You are given an array where prices[i] represents the stock price on day i. You can buy and sell the stock multiple times, but you cannot hold more than one share at a time. The goal is to compute the maximum profit you can achieve by choosing optimal buy and sell days.
This problem is fundamentally about capturing every profitable upward price movement. Instead of searching for a single global maximum transaction, you accumulate profit across multiple smaller trades. The structure of the array and the ability to perform unlimited transactions makes Greedy strategies particularly effective.
Approach 1: Peak-Valley Approach (O(n) time, O(1) space)
This approach explicitly identifies local valleys (buy points) and local peaks (sell points). Iterate through the array while skipping descending prices until you find a valley. Once a valley is found, continue scanning forward until the prices stop increasing, which marks the peak. The profit for that segment is peak - valley. Add it to the total profit and continue scanning the remaining array.
The key insight is that every increasing sequence can be treated as a profitable transaction. Instead of computing all pairs, the algorithm captures profit from each upward segment. This approach mirrors how traders reason about trends and makes the transaction boundaries explicit. Time complexity is O(n) since each element is visited at most once, and space complexity is O(1).
Approach 2: Simple One-Pass Greedy (O(n) time, O(1) space)
The peak-valley logic can be simplified further. Any time prices[i] > prices[i-1], you add the difference prices[i] - prices[i-1] to the profit. This effectively captures the profit of every upward step. Multiple consecutive increases naturally accumulate into the same total profit as buying at the valley and selling at the peak.
The insight is that (peak - valley) equals the sum of all incremental increases between them. For example, if prices go from 1 → 3 → 5, the profit (5-1) equals (3-1) + (5-3). By adding positive differences during a single pass, the algorithm automatically collects the optimal profit without explicitly detecting valleys or peaks.
This greedy strategy is the cleanest implementation and the one most commonly expected in interviews. It runs in O(n) time with O(1) space and requires only a single loop over the array.
Although the reasoning can also be framed using Dynamic Programming (tracking hold vs. not-hold states), the DP transitions simplify directly into the greedy rule above when unlimited transactions are allowed.
Recommended for interviews: The one-pass greedy solution is the expected answer. It demonstrates that you recognize the additive property of incremental price increases and can reduce the problem to a single linear scan. Mentioning the peak-valley reasoning first helps explain why the greedy rule works, then implementing the one-pass version shows strong optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Peak-Valley Approach | O(n) | O(1) | Useful when you want explicit buy/sell boundaries and clearer reasoning about trading segments. |
| One-Pass Greedy (Sum of Positive Differences) | O(n) | O(1) | Best for interviews and production code due to its minimal logic and single-pass implementation. |