LeetCode #123 Hard

Best Time to Buy and Sell Stock III

Max profit using at most two non-overlapping buy-sell transactions.

dynamic-programmingarraystate-machine

02

Intuition

💡

The obvious-looking shortcut is to find the two best individual gains anywhere in the array, say the biggest rise on the left half and the biggest rise on the right half, and add them. Those two windows can OVERLAP in time, which is illegal: the second buy has to happen strictly after the first sell closes out. Instead track four running states, buy1, sell1, buy2, sell2, where each is built only from the state immediately before it in the chain. buy2 can only spend money that sell1 already banked, so the ordering constraint is enforced by construction rather than by checking indices afterward.

03

Approach

1

Four states, one dependency chain

buy1 = best cash position after one purchase, sell1 = best profit after closing that one trade, buy2 = best cash position after a second purchase funded out of sell1's profit, sell2 = best profit after closing a second trade. Initialize buy1 = buy2 = -prices[0], sell1 = sell2 = 0.

2

Update in dependency order each day

For each day's price: buy1 = max(buy1, -price); sell1 = max(sell1, buy1 + price); buy2 = max(buy2, sell1 - price); sell2 = max(sell2, buy2 + price). Because buy2 reads sell1 and sell2 reads buy2, using the SAME day's already-updated sell1/buy2 is fine here since a buy and sell can't happen on the same day profitably in a way that breaks this, and it keeps the whole thing to one pass.

3

Answer is sell2

sell2 is a running max seeded from sell1's history, so if a second trade never helps, sell2 simply never rises above sell1 and the recurrence naturally falls back to using only one transaction (or zero).

04

Solution & live demo

python

▶1class Solution:
▶2    def maxProfit(self, prices: list[int]) -> int:
▶3        n = len(prices)
▶4        if n < 2:
▶5            return 0
▶6        buy1 = buy2 = -prices[0]
▶7        sell1 = sell2 = 0
▶8        for i in range(1, n):
▶9            buy1 = max(buy1, -prices[i])
▶10            sell1 = max(sell1, buy1 + prices[i])
▶11            buy2 = max(buy2, sell1 - prices[i])
▶12            sell2 = max(sell2, buy2 + prices[i])
▶13        return sell2

05

Edge cases

Strictly decreasing prices

buy1, buy2 chase the lowest price but sell1, sell2 never exceed 0, so the answer correctly stays 0 with no forced losing trade.

Only one profitable dip-then-rise in the whole array

sell2 stays equal to sell1 throughout since a second trade never improves on it, correctly reducing to the single-transaction answer.

Fewer than 2 price points

With 0 or 1 prices there is no valid transaction; the loop from day 1 onward simply does not run and profit stays 0.

Two disjoint profitable windows

buy2 only ever draws funds from sell1, which already reflects a closed first trade, so the two captured gains cannot overlap in time.

06

Complexity

Time

O(n)

Space

O(1)

Four rolling scalars replace a k=2 transaction DP table.