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 are given an array where prices[i] represents the stock price on day i. You can complete at most two transactions (buy then sell). The goal is to compute the maximum profit possible without holding more than one stock at a time.
Approach 1: Dynamic Programming with 4 State Variables (O(n) time, O(1) space)
This approach models the trading process as four states: first buy, first sell, second buy, and second sell. Each state represents the best profit achievable after that operation. While iterating through the price array, update the states using simple max comparisons such as firstBuy = max(firstBuy, -price) and firstSell = max(firstSell, firstBuy + price). The key insight is that every transaction builds on the previous one, so the second buy depends on the profit from the first sell. This reduces the entire dynamic programming formulation into four running variables, giving an optimal O(n) solution with constant memory.
Approach 2: Two Arrays for Tracking Left and Right Profits (O(n) time, O(n) space)
This strategy splits the problem into two independent subproblems. First, traverse the array from left to right and compute leftProfit[i], the maximum profit achievable with one transaction in the range [0, i]. Then traverse from right to left to compute rightProfit[i], the best profit for one transaction in [i, n-1]. Combining these two arrays lets you evaluate every possible split point where the first transaction happens before the second. The final answer is the maximum value of leftProfit[i] + rightProfit[i]. This technique works well when reasoning about prefix and suffix profits in array problems.
Recommended for interviews: The 4‑state dynamic programming solution is usually expected in interviews because it demonstrates strong understanding of dynamic programming state transitions and optimization. The two‑array method is easier to reason about conceptually, but the constant‑space DP version shows deeper algorithmic skill and cleaner implementation.
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.
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.
Time Complexity: O(n), as we iterate twice through prices.
Space Complexity: O(n), due to the use of two auxiliary arrays.
We define the following variables:
f1 represents the maximum profit after the first purchase of the stock;f2 represents the maximum profit after the first sale of the stock;f3 represents the maximum profit after the second purchase of the stock;f4 represents the maximum profit after the second sale of the stock.During the traversal, we directly calculate f1, f2, f3, f4. We consider that buying and selling on the same day will result in a profit of 0, which will not affect the answer.
Finally, return f4.
The time complexity is O(n), where n is the length of the prices array. The space complexity is O(1).
| 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. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 4 State Variables | O(n) | O(1) | Best overall solution. Preferred in interviews due to optimal space usage and clean DP transitions. |
| Two Arrays for Left and Right Profits | O(n) | O(n) | Useful for understanding the split of two transactions and easier to visualize prefix/suffix profits. |
Best Time to Buy and Sell Stock III | Leetcode #123 • Techdose • 79,573 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