Best Time to Buy and Sell Stock III — At Most 2 Transactions State Machine

Problem Statement#

You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve. You may complete at most two transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

Example 1:

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

Example 2:

Input:  prices = [1, 2, 3, 4, 5]
Output: 4
Explanation: Buy on day 1 (price=1), sell on day 5 (price=5). Profit = 4.
             One transaction is enough — the second adds nothing.

Example 3:

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Only decreasing prices — no profitable transaction.

Why This Problem Matters#

Stock III (at most 2 transactions) is rated Hard and is a common final question in FAANG stock-problem sequences. It cannot be solved with a simple greedy because the two transactions can overlap in complex ways across the price array.

The key technique is a 4-state state machine: buy1, sell1, buy2, sell2 — representing the best achievable profit in each state after processing the current day. The transitions capture how each state evolves as prices change.

This problem is also the conceptual bridge to LC 188 (at most k transactions): once you understand the 4-variable 2-transaction state machine, generalizing to k transaction pairs is mechanical.

Google and Amazon frequently use this problem to distinguish candidates who truly understand DP state design from those who can only apply memorized formulas.

The Core Insight#

State machine with 4 states:

After processing each day's price, the system can be in one of 4 states:

1. buy1: Best profit achievable after the first buy (holding after 1st purchase)
2. sell1: Best profit achievable after the first sell (not holding, 1 complete transaction)
3. buy2: Best profit achievable after the second buy (holding after 2nd purchase)
4. sell2: Best profit achievable after the second sell (not holding, 2 complete transactions)

Transitions (updated each day for price p):

buy1  = max(buy1,  -p)           # buy for the first time
sell1 = max(sell1, buy1 + p)     # sell the first holding
buy2  = max(buy2,  sell1 - p)    # buy again using sell1 profit
sell2 = max(sell2, buy2 + p)     # sell the second holding

Base cases:

• buy1 = -infinity (haven't bought yet)
• sell1 = 0 (no completed transaction yet)
• buy2 = -infinity (haven't started second transaction)
• sell2 = 0 (no second completed transaction)

Answer: sell2 after all days.

Key insight about sell2: When one transaction is sufficient, sell1 can be used for both transactions: buy2 = max(buy2, sell1 - p) allows the second buy to happen at the same time as the first sell, effectively collapsing to a single transaction.

Building the DP Solution#

Alternative: 2D DP approach: For each day i and transaction count k in {0, 1, 2}, track holding status:

dp[i][k][0] = max profit on day i, k transactions used, not holding
dp[i][k][1] = max profit on day i, k transactions used, holding

This generalizes to k transactions (used in LC 188) but is more memory-intensive than the 4-variable state machine.

Optimized: 4-variable state machine:

def maxProfit(prices):
    buy1 = buy2 = float('-inf')
    sell1 = 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

Visual Dry Run#

Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]

Answer: sell2 = 6

Optimized Solution#

Python#

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # 4-state state machine: buy1, sell1, buy2, sell2
        buy1 = float('-inf')   # best profit after buying once (holding)
        sell1 = 0              # best profit after selling once (not holding)
        buy2 = float('-inf')   # best profit after buying twice (holding)
        sell2 = 0              # best profit after selling twice (not holding)
 
        for price in prices:
            # Order matters: update in sequence so each state uses the previous day's values
            # (except buy1 which only depends on itself — buying for the first time)
            buy1  = max(buy1,  -price)           # first buy
            sell1 = max(sell1, buy1 + price)     # first sell (uses updated buy1 — valid: same day buy-sell = 0 profit)
            buy2  = max(buy2,  sell1 - price)    # second buy (use first sell profit)
            sell2 = max(sell2, buy2 + price)     # second sell
 
        return sell2

JavaScript#

var maxProfit = function(prices) {
    let buy1  = -Infinity;
    let sell1 = 0;
    let buy2  = -Infinity;
    let sell2 = 0;
 
    for (const price of prices) {
        buy1  = Math.max(buy1,  -price);
        sell1 = Math.max(sell1, buy1 + price);
        buy2  = Math.max(buy2,  sell1 - price);
        sell2 = Math.max(sell2, buy2 + price);
    }
 
    return sell2;
};

Complexity Analysis#

Common Mistakes#

1. Updating the states in the wrong order. The 4 states must be updated in order: buy1, sell1, buy2, sell2. sell1 depends on buy1, buy2 depends on sell1, and sell2 depends on buy2. Reversing or shuffling the order produces incorrect results because later states would use same-day values instead of previous-day values.

2. Not allowing same-day buy-sell-buy sequences. The problem allows selling and re-buying on the same day. This means buy2 can be updated using the same-day sell1. In the 4-variable approach, this is automatically handled by the update order: after updating sell1, we immediately use it in buy2.

3. Initializing all states to 0. buy1 and buy2 must be initialized to -infinity (haven't bought yet — state unreachable). Initializing to 0 incorrectly means "bought for free," inflating profits by the buy price.

4. Returning buy2 instead of sell2. The answer is the maximum profit when NOT holding any stock. buy2 represents the state where you are still holding the second stock — an unrealized profit. Always return sell2.

5. Confusing "at most 2" with "exactly 2". "At most 2 transactions" means 0, 1, or 2 complete buy-sell pairs. The state machine handles this naturally: if the second transaction adds no profit, sell2 will equal sell1 (the second buy-sell nets to 0 and is effectively skipped).

Interview Tips#

• Draw the state machine diagram with arrows. Four nodes connected: buy1 -> sell1 -> buy2 -> sell2. Each arrow is triggered by a sell/buy decision.
• Explain the initialization: "buy1 = buy2 = -infinity because we haven't bought yet. sell1 = sell2 = 0 because zero transactions completed means zero profit."
• Walk through the update order: "I update buy1 first, then sell1 using buy1, then buy2 using sell1, then sell2 using buy2 — a pipeline."
• Show the generalization: "For k transactions, I'd have k buy and k sell variables, updated in the same pipeline. This is exactly LC 188."
• For the 2D DP approach: "Alternatively, dp[k][0/1] where k is 0/1/2 transactions and 0/1 is hold/not-hold — same idea, more memory."

Follow-up Questions#

Q: How does this generalize to k transactions? (LC 188) Use arrays buy[k] and sell[k]. For each day, update all k pairs in order: buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price).

Q: What if the 2-transaction limit is very large (k >= n/2)? If k >= n/2, you can effectively make unlimited transactions. Fall back to the Stock II greedy: collect all positive adjacent differences.

Q: What if you have transaction fees? (See LC 714) In the sell transitions, subtract the fee: sell1 = max(sell1, buy1 + price - fee) and sell2 = max(sell2, buy2 + price - fee).

Q: What if you must make exactly 2 transactions? This variant is rarely asked. One approach: compute max profit for each partition of days (first transaction in days 0..i, second in days i..n-1) and sum. O(n) with prefix max-profit and suffix max-profit arrays.

Key Takeaways#

• Four states: buy1, sell1, buy2, sell2 — initialized to -inf, 0, -inf, 0.
• Update each day in order: buy1 = max(buy1, -p), sell1 = max(sell1, buy1+p), buy2 = max(buy2, sell1-p), sell2 = max(sell2, buy2+p).
• The answer is sell2 — the maximum profit after at most 2 complete transactions.
• Update order is critical: each state must see the previous state's updated value within the same day's pipeline.
• "At most 2" means the second transaction is optional — if it adds no profit, sell2 remains equal to sell1.
• This 4-variable pattern directly generalizes to k-transaction arrays (LC 188): just extend to buy[k] and sell[k] arrays.