Best Time to Buy and Sell Stock III Solution

Problem

Given a list of daily stock prices, find the maximum profit achievable using at most two buy-sell transactions. You must sell before buying again — you can never hold more than one share at a time.

Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output: 6
Explanation: Buy at price 0 (day 4), sell at 3 (day 6), profit = 3. Buy at 1 (day 7), sell at 4 (day 8), profit = 3. Total = 6.

A case where one transaction beats two: prices = [1, 2, 3, 4, 5] → output 4 (buy at 1, sell at 5).

Intuition

Split the problem into two independent single-transaction subproblems: what's the best you can do in the first half of the timeline, and the best you can do in the second half? The split point can be any day, and the two halves are allowed to overlap at that day (sell first stock, buy second stock same day). Alternatively, model the full problem as four sequential states — buy1, sell1, buy2, sell2 — and greedily propagate the best value into each state as you scan prices once.

Approach 1: Split-Day Precomputation

Precompute the best single-transaction profit ending at or before each day (forward pass), and the best single-transaction profit starting at or after each day (backward pass). Combine the two arrays at every split point to find the best pairing.

Forward pass: scan left to right, tracking the running minimum price. profit_ending_by[i] = best profit from one trade in prices[0..i].
Backward pass: scan right to left, tracking the running maximum price. profit_starting_from[i] = best profit from one trade in prices[i..n-1].
Answer = max over all i of profit_ending_by[i] + profit_starting_from[i].

1def maxProfit(prices: list[int]) -> int:
2    n = len(prices)
3    profit_ending_by = [0] * n
4    min_price_seen = prices[0]
5    for i in range(1, n):
6        min_price_seen = min(min_price_seen, prices[i])
7        profit_ending_by[i] = max(profit_ending_by[i - 1], prices[i] - min_price_seen)
8
9    profit_starting_from = [0] * n
10    max_price_ahead = prices[-1]
11    for i in range(n - 2, -1, -1):
12        max_price_ahead = max(max_price_ahead, prices[i])
13        profit_starting_from[i] = max(profit_starting_from[i + 1], max_price_ahead - prices[i])
14
15    return max(profit_ending_by[i] + profit_starting_from[i] for i in range(n))

Time: O(n) — three linear passes over the array.
Space: O(n) — two auxiliary arrays of length n.

Approach 2: State Machine DP

Model the problem as four states, each tracking the best "net cash" achievable after reaching that event. Process every price once and cascade updates through all four states in order.

first_buy = best net cash after the first purchase (-price for a fresh buy).
first_sell = best profit after completing the first sale.
second_buy = best net cash after reinvesting first-sale profits into a second purchase.
second_sell = best total profit after completing the second sale.
Updating in order first_buy → first_sell → second_buy → second_sell within each iteration ensures that buying and selling on the same day is handled correctly.

1def maxProfit(prices: list[int]) -> int:
2    first_buy = float('-inf')   # sentinel: haven't bought yet
3    first_sell = 0
4    second_buy = float('-inf')  # sentinel: haven't done second buy yet
5    second_sell = 0
6
7    for price in prices:
8        first_buy = max(first_buy, -price)                  # buying here costs `price`
9        first_sell = max(first_sell, first_buy + price)     # selling here recovers `price`
10        second_buy = max(second_buy, first_sell - price)    # re-buy after locking in first profit
11        second_sell = max(second_sell, second_buy + price)  # final sale
12    
13    return second_sell

Time: O(n) — single pass over the prices array.
Space: O(1) — only four integer variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Split-Day Precomputation	O(n)	O(n)	When the two-pass structure is easier to reason about and verify
State Machine DP	O(n)	O(1)	Preferred in interviews — minimal space and a single clean loop

Common Mistakes

Running the single-transaction algorithm twice on the full array — applying the Stock I greedy (track running min, compute max spread) a second time starting where the first left off doesn't work; the first transaction must be confined to a prefix so the second can use the remaining suffix.
Initializing buy states to 0 instead of a large negative sentinel — buying a stock costs money, so the net-cash variable after buying must start negative. Initializing to 0 tells the algorithm you received the stock for free, inflating every downstream profit by the actual purchase price.
Confusing "at most 2 transactions" with "exactly 2" — if a single transaction earns more than any two-transaction split, the answer should be that single profit. The state machine handles this automatically because second_sell >= first_sell >= 0, so unused transactions contribute 0.
Off-by-one in the split-day approach — profit_ending_by[i] must allow selling on day i, and profit_starting_from[i] must allow buying on day i. Using strict inequalities at the boundary misses the valid scenario of selling the first stock and buying the second on the same day.
Updating state machine variables in reverse order — the cascade must go first_buy → first_sell → second_buy → second_sell. Reversing it means later states see stale values from the previous iteration, which disallows valid same-day sell-then-buy transitions and produces wrong results on some inputs.

Best Time to Buy and Sell Stock III — Solution