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)
Starting from the second day, if the stock price is higher than the previous day, buy on the previous day and sell on the current day to make a profit. If the stock price is lower than the previous day, do not buy or sell. In other words, buy and sell on all rising trading days, and do not trade on all falling trading days. The final profit will be the maximum.
The time complexity is O(n), where n is the length of the prices array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
We define f[i][j] as the maximum profit after trading on the ith day, where j indicates whether we currently hold the stock. When holding the stock, j=0, and when not holding the stock, j=1. The initial state is f[0][0]=-prices[0], and all other states are 0.
If we currently hold the stock, it may be that we held the stock the day before and do nothing today, i.e., f[i][0]=f[i-1][0]. Or it may be that we did not hold the stock the day before and bought the stock today, i.e., f[i][0]=f[i-1][1]-prices[i].
If we currently do not hold the stock, it may be that we did not hold the stock the day before and do nothing today, i.e., f[i][1]=f[i-1][1]. Or it may be that we held the stock the day before and sold the stock today, i.e., f[i][1]=f[i-1][0]+prices[i].
Therefore, we can write the state transition equation as:
$
\begin{cases}
f[i][0]=max(f[i-1][0],f[i-1][1]-prices[i])\
f[i][1]=max(f[i-1][1],f[i-1][0]+prices[i])
\end{cases}
The final answer is f[n-1][1], where n is the length of the prices array.
The time complexity is O(n), and the space complexity is O(n). Here, n$ is the length of the prices array.
We can find that in Solution 2, the state of the ith day is only related to the state of the i-1th day. Therefore, we can use only two variables to maintain the state of the i-1th day, thereby optimizing the space complexity to O(1).
The time complexity is O(n), where n is the length of the prices array. The space complexity is 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) |
| Greedy Algorithm | — |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| 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