Best Time to Buy and Sell Stock III
Find the maximum profit from at most two buy-and-sell transactions in one pass, keeping the best profit after the first buy, first sell, second buy and second sell.
Problem Understanding
Best Time to Buy and Sell Stock III (LeetCode 123): given daily prices, return the maximum profit from at most two transactions. You must sell before you buy again.
Examples: [3,3,5,0,0,3,1,4] → 6; [1,2,3,4,5] → 4; [7,6,4,3,1] → 0.
The Intuition: Four Stages, Each Fed by the One Before
Your money goes through four stages in order, and each day every stage either stays or is reached from the stage before it:
- buy1: pay today's price for the first share.
- sell1: receive today's price after buy1.
- buy2: pay today's price out of sell1's profit.
- sell2: receive today's price after buy2.
The best value of the last stage is the answer. With any k this becomes Best Time to Buy and Sell Stock IV; with one trade it is Best Time to Buy and Sell Stock.
Interactive Walkthrough
AT MOST 2 TRADES
BEFORE DAY 0
day
0
1
2
3
4
5
6
7
price
buy 1
sell 1
buy 2
sell 2
day
:
k
2
profit
:
At most 2 trades. Before day 0 no share can be held (buy = −∞) and every sell is 0
Next
Day 0, price 3: buy 1 = 0 − 3 = −3; buy 2 = 0 − 3 = −3
prices
Each column is a day and each row one of the four stages; solid cells improved that day. Try Three swings: three rises of 4, but the answer stops at 8 because only two trades are allowed.
Dry Run Table
Input: [3,3,5,0,0,3,1,4].
| Day | Price | What improves |
|---|---|---|
| 0 | 3 | buy1 = −3, buy2 = −3 |
| 1 | 3 | nothing |
| 2 | 5 | sell1 = 2, sell2 = 2 |
| 3 | 0 | buy1 = 0, buy2 = 2 − 0 = 2 |
| 4 | 0 | nothing |
| 5 | 3 | sell1 = 3, sell2 = 2 + 3 = 5 |
| 6 | 1 | nothing |
| 7 | 4 | sell1 = 4, sell2 = 2 + 4 = 6 |
Answer: 6.
The Solution Template
Four variables, one pass.
Best Time to Buy and Sell Stock III Code
1var maxProfit = function(prices) {2 let buy1 = -Infinity, buy2 = -Infinity;3 let sell1 = 0, sell2 = 0;4 for (const price of prices) {5 buy1 = Math.max(buy1, -price);6 sell1 = Math.max(sell1, buy1 + price);7 buy2 = Math.max(buy2, sell1 - price);8 sell2 = Math.max(sell2, buy2 + price);9 }10 return sell2;11};
Edge Cases & Common Mistakes
- Prices only fall: no trade is worth making; every sell stays 0.
- One long rise: one trade is optimal; sell2 equals sell1.
- Summing the two biggest single rises: they may overlap or be split wrongly; the four-state update avoids that.
- Initialising buy to 0: that pretends you own a free share; use −∞.
- Treating it as Stock II: adding every rise allows unlimited trades and overcounts once there are more than two rises.
Summary
Track buy1, sell1, buy2 and sell2; each day each takes the better of staying and being reached from the stage before. Return sell2. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet