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.
The Peak-Valley Approach aims to identify opportunities where a buy (at a valley) and a sell (at a peak) transaction yields profit. The idea is to take advantage of every upward trend between valleys and peaks and sum up the differences.
The code iterates over the price array. Whenever a profit opportunity is identified (when today's price is higher than yesterday's), the difference is added to the total profit. This maximizes profit by summing up all 'up-hill' gains directly.
Time Complexity: O(n), where n is the number of prices.
Space Complexity: O(1), no additional space is used.
The simple one-pass greedy approach makes a decision on each day based on whether the price will go up (buy or hold) or down (sell or do nothing). This maximizes profit by keeping solutions simple, efficient and using the greedy approach to sum up all local gains.
This solution follows a greedy logic where each upward opportunity is utilized. For each day, if the current day's price is greater than the previous day's, the difference is added to the profit.
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Peak-Valley Approach | Time Complexity: O(n), where n is the number of prices. |
| Simple One-Pass Greedy Approach | Time Complexity: O(n) |
| 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. |
Best Time to Buy and Sell a Stock II - Leetcode 122 - Python • NeetCode • 142,874 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor