This problem requires calculating the maximum achievable profit with at most two non-overlapping stock transactions. Use state transition dynamic programming to track profits across days and transaction counts. The key is to maintain separate states for holding and not holding stock across both transactions to avoid invalid overlaps.
Problem Statement
You are given an array of integers where each element represents the price of a stock on a specific day. You can perform at most two transactions, meaning you can buy and sell the stock twice at most. Each transaction must consist of a buy followed by a sell, and you cannot hold multiple stocks at once.
Your goal is to find the maximum total profit achievable under these rules. Ensure that each transaction is non-overlapping, and consider the optimal combination of the two transactions across all days.
Examples
Example 1
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
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
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
In this case, no transaction is done, i.e. max profit = 0.
Constraints
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 105
Solution Approach
Define State Transitions
Model four states: first buy, first sell, second buy, and second sell. Each state depends on the previous day’s state, capturing the best profit possible while respecting the at-most-two-transactions rule.
Iterate Through Prices
Traverse the price array, updating each state based on whether you buy or sell on that day. For example, first buy is the max of previous first buy and negative current price, while first sell is the max of previous first sell and first buy plus current price.
Return Maximum Profit
After processing all days, the maximum profit is the value of the second sell state, representing the profit after completing up to two optimal transactions without overlap.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) since each day updates a fixed number of states. Space complexity is O(1) because only four variables are maintained instead of storing all intermediate states.
What Interviewers Usually Probe
- Look for correct handling of up to two transactions without simultaneous holds.
- Check if state transitions correctly track buy and sell decisions for both transactions.
- Watch for off-by-one errors when updating profits across days.
Common Pitfalls or Variants
Common pitfalls
- Attempting to store profits for all transaction counts in an array can increase space unnecessarily.
- Overwriting states in the wrong order can cause incorrect profit calculations.
- Failing to consider zero transactions as a valid maximum profit scenario.
Follow-up variants
- At most k transactions instead of two, requiring generalized DP with k states.
- Allowing transaction fees, adjusting state updates to subtract fees when selling.
- Restricting cooldown days between transactions, requiring extra states to track cooldown.
How GhostInterview Helps
- Provides step-by-step state transition guidance to track two transactions without overlap.
- Highlights potential failure modes like overwriting states or miscounting transactions.
- Illustrates efficient O(n) iteration patterns tied directly to the array and dynamic programming approach.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy for Best Time to Buy and Sell Stock III?
Use state transition dynamic programming with four states: first buy, first sell, second buy, and second sell, iterating through prices to maximize profit.
Can I complete multiple transactions simultaneously?
No, each buy must be followed by a sell before initiating the next transaction.
What if the price array is strictly decreasing?
In that case, no transactions should be made, and the maximum profit is 0.
How does GhostInterview prevent common DP mistakes?
It tracks state updates in order, preventing overwriting and ensuring each transaction is counted correctly.
Is this approach scalable for large arrays?
Yes, it runs in O(n) time and O(1) space, making it efficient even for arrays up to 105 elements.
Need direct help with Best Time to Buy and Sell Stock III instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Best Time to Buy and Sell Stock III from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Maximize stock profit by using a greedy approach to buy and sell multiple times, with state transition dynamic programming.
Open problem page#121 Best Time to Buy and Sell StockMaximize stock profit by identifying the optimal buy and sell days using dynamic programming.
Open problem page#120 TriangleGiven a triangle, return the minimum path sum from top to bottom, moving to adjacent numbers in the row below.
Open problem page