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 848,237 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 receive an array prices where prices[i] represents the stock price on day i. You can buy and sell the stock multiple times, but you must sell before buying again. The goal is to compute the maximum profit achievable across all transactions.
Approach 1: Peak-Valley Approach (O(n) time, O(1) space)
This approach explicitly finds every profitable transaction by identifying valleys (local minimums) and peaks (local maximums). You iterate through the array and first move forward while prices are decreasing to find a valley (buy point). Then continue moving while prices increase to locate the peak (sell point). The difference between the peak and valley is one transaction's profit. Repeat until you reach the end of the array.
The key insight: any increasing sequence of prices represents a profitable trade window. Instead of trying all buy/sell combinations, you simply capture the lowest point before an upward trend and the highest point before it drops. This approach clearly models real trading behavior and helps when you want to visualize each transaction rather than just compute total profit.
Approach 2: Simple One-Pass Greedy (O(n) time, O(1) space)
The optimal solution uses a greedy observation: every upward price difference can be treated as profit. If prices[i] > prices[i-1], you add prices[i] - prices[i-1] to the total. This effectively simulates buying yesterday and selling today whenever the price increases.
This works because any long increasing sequence (for example 1 → 2 → 3 → 4) produces the same profit whether you trade once (buy at 1, sell at 4) or capture each step (1→2, 2→3, 3→4). The greedy accumulation avoids explicit peak detection and reduces the logic to a single pass through the array.
The greedy interpretation is also equivalent to the simplified state transition from dynamic programming formulations of the stock trading problem. Instead of tracking full DP states, the monotonic price increase rule captures the optimal decision locally.
Recommended for interviews: The one-pass greedy approach is what most interviewers expect. It shows you recognized the core insight that every positive price difference contributes to the final profit. Mentioning the peak-valley interpretation first can help demonstrate reasoning about transaction boundaries, but the greedy O(n) solution with constant space is the cleanest implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Peak-Valley Approach | O(n) | O(1) | When you want to explicitly model each buy and sell transaction |
| One-Pass Greedy | O(n) | O(1) | Best general solution for interviews and production code |