Best Time to Buy and Sell Stock III: At Most Two Transactions

You are given an array prices where prices[i] is the price of a stock on day i. You may complete at most two transactions (buy then sell, buy then sell). You cannot hold more than one share at a time (you must sell before buying again). Find the maximum profit.

This is LeetCode 123: Best Time to Buy and Sell Stock III, a hard problem that builds directly on the single-transaction version. The key leap is tracking four states instead of two, all updated greedily in a single pass.

Why brute force breaks down

You could try all possible pairs of non-overlapping transactions. Pick a split point k, solve "best single transaction in prices[0..k]" and "best single transaction in prices[k..n-1]", and take the max over all split points. That works in O(n) per split with precomputation, giving O(n) total if you precompute left-max and right-max arrays.

But there is an even cleaner approach that uses O(1) space and a single pass. No auxiliary arrays, no split points.

The key insight: four states in one pass

Think of the problem as a state machine. At any point during your scan, you are in one of four possible states:

• buy1: the best (most negative) cost of your first purchase so far. You want to buy as cheaply as possible, so this tracks max(-price) across all days seen.
• sell1: the best profit after completing the first transaction. At each day, you could sell at today's price after having bought at your best buy1 price.
• buy2: the best position after buying the second stock. This factors in the profit from the first transaction: you spend price but you already earned sell1, so the effective cost is sell1 - price.
• sell2: the best total profit after completing both transactions.

On each day, you update all four in order:

buy1  = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2  = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)

That is it. Four variables, four updates, one loop.

Walking through the example

Let's trace prices = [3, 3, 5, 0, 0, 3, 1, 4] step by step. Watch how the four states evolve. buy1 stores the negative of the best first purchase price (so buy1 = 0 means you bought at price 0). buy2 stores sell1 - price, the net position after the first profit minus the second purchase cost.

The final value of sell2 is 6. That corresponds to buying at 0, selling at 3 (profit 3), then buying at 1, selling at 4 (profit 3), for a total of 6.

The code

def max_profit(prices):
    buy1 = float('-inf')
    sell1 = 0
    buy2 = float('-inf')
    sell2 = 0

    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)

    return sell2

Each iteration does four constant-time comparisons. No nested loops, no extra arrays.

Why updating in order on the same day is correct

You might worry that updating buy1 and then immediately using it in sell1 on the same day allows a "buy and sell on the same day" situation. That is fine. Buying and selling on the same day produces zero profit, which never beats a real profit. The max operation filters it out. The same logic applies to sell1 feeding into buy2: if the first transaction has zero profit, buy2 just behaves like a standalone first buy.

Complexity analysis

Time: O(n). One pass through the array. Each element requires four comparisons and at most four updates, all O(1).

Space: O(1). Four variables regardless of input size. No auxiliary arrays, no hash maps, no stacks.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• Only one profitable transaction: if the best result uses a single transaction, sell2 still captures it. The second buy/sell pair contributes zero, so sell2 equals sell1.
• Decreasing prices like [5, 4, 3, 2, 1]: no profitable trade exists. All sell values stay at 0. Return 0.
• All same prices like [3, 3, 3, 3]: every buy-sell pair yields zero profit. Return 0.
• Monotonically increasing like [1, 2, 3, 4, 5]: one transaction (buy at 1, sell at 5) gives profit 4. The second transaction adds nothing. sell2 = 4.
• Two clear valleys and peaks: the classic case where two separate transactions beat one spanning transaction.

The building blocks

This problem is built on two reusable patterns:

State machine DP. Instead of thinking about which days to buy and sell, you model the problem as transitions between states. Each state represents a phase of the trading process (holding vs. not holding, first trade vs. second trade). The DP recurrence updates each state greedily. This pattern appears in many stock trading variants and in problems like "Best Time to Buy and Sell Stock with Cooldown" and "Best Time to Buy and Sell Stock with Transaction Fee."

Multi-transaction tracking. The idea of running multiple interleaved trackers in a single pass generalizes beyond two transactions. For k transactions, you would use 2k state variables (k buys and k sells). When k is small and fixed, this stays O(1) space. The four-variable version here is the special case for k = 2.

Once you internalize these patterns, the jump from the single-transaction stock problem to the two-transaction version becomes natural. It is the same greedy-in-one-pass idea, just with more state to carry.

From understanding to recall

Reading through this solution and nodding along is the easy part. The hard part is reproducing it under pressure, from scratch, without looking at a reference. Can you set up the four variables? Do you remember the update order? Do you remember why the order is safe?

Spaced repetition closes that gap. Instead of solving this problem once and forgetting the details in a week, you revisit the core pattern at increasing intervals. Each time you write the four-state loop from memory. After a few repetitions, it is automatic.

The state machine DP pattern and multi-transaction tracking are two of roughly 60 reusable building blocks that appear across hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding through problems and hoping they stick.

Related posts

• Best Time to Buy and Sell Stock - The single-transaction version that this problem builds on
• Maximum Subarray - Another one-pass DP problem where you carry state forward greedily