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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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) | 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 |
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 848,237 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