You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
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. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 105Problem Overview: You receive an array prices where prices[i] is the stock price on day i. You may complete at most two buy-sell transactions. The goal is to compute the maximum possible profit while respecting the rule that you must sell before buying again.
Approach 1: Dynamic Programming with 4 State Variables (O(n) time, O(1) space)
This approach models the problem as four sequential states representing the best profit after each operation: first buy, first sell, second buy, and second sell. As you iterate through the array once, update these states using simple max comparisons. For example, firstBuy tracks the lowest effective purchase cost, firstSell stores the best profit after selling once, secondBuy represents reinvesting after the first profit, and secondSell tracks the final maximum profit. Each price updates the states in order, ensuring that earlier transaction results feed into later ones. This method uses concepts from dynamic programming but compresses the DP table into constant space, making it the most efficient implementation.
Approach 2: Two Arrays for Tracking Left and Right Profits (O(n) time, O(n) space)
This strategy splits the timeline into two independent transactions. First, scan from left to right and compute leftProfit[i], the best profit achievable with one transaction between day 0 and i. Track the minimum price so far and update the profit greedily. Then scan from right to left to compute rightProfit[i], the maximum profit achievable with one transaction between day i and the last day by tracking the maximum future price. The final answer is the best combination of leftProfit[i] + rightProfit[i] across all split points. This method relies on efficient traversal of the array and builds a clear mental model of how two transactions interact across the timeline.
Recommended for interviews: The 4-state dynamic programming solution is the one interviewers typically expect. It demonstrates strong understanding of dynamic programming state transitions and space optimization. The two-array method is easier to reason about initially and helps validate your intuition, but the constant-space DP version shows deeper algorithmic maturity.
This approach utilizes dynamic programming with four state variables to track the profit in various stages of transactions: before the first buy, after the first buy (before the sell), after the first sell (before the second buy), and after the second buy (before the final sell). By iterating over the prices array, we update these states with the maximum profit achievable at each step.
This solution initializes four state variables representing the different transaction stages. We iterate over the price list to update these states, maximizing profit at each step. The final state, secondSell, holds the maximum profit obtainable.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of days (prices length).
Space Complexity: O(1), constant space used regardless of input size.
This approach involves creating two arrays that store the maximum profit achievable from the left side to each index and from each index to the right in the prices array. Combining these two arrays helps derive the total maximum profit achievable through two transactions.
This C solution uses two auxiliary arrays to track maximal profit potential from either direction along the price sequence. Profit amounts are compiled crosswise to determine peak profitability over the entire period.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as we iterate twice through prices.
Space Complexity: O(n), due to the use of two auxiliary arrays.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with 4 State Variables | Time Complexity: O(n), where n is the number of days (prices length). |
| Approach 2: Two Arrays for Tracking Left and Right Profits | Time Complexity: O(n), as we iterate twice through prices. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 4 State Variables | O(n) | O(1) | Best for interviews and production code when you want the optimal constant-space solution |
| Left and Right Profit Arrays | O(n) | O(n) | Good for understanding the two-transaction split and easier debugging |
DP 37. Buy and Sell Stocks III | Recursion to Space Optimisation • take U forward • 206,958 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor