Free lesson · DSA Mastery - Interview Prep, End to End

Best Time to Buy and Sell Stock III

Hard6 min readdsadynamic-programming

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III restricts the number of transactions to at most two: the DP gains a transaction-count dimension. State = (position, transactions used, holding), total 2 · 3 = 6 states. Recurrence enumerates buy/sell/hold/idle transitions across the augmented state. It demonstrates adding a transaction-count dimension to the State Machine DP and shows that bounded-transaction problems extend the framework cleanly. We present the 6-variable rolling DP (canonical) and the elegant 4-variable formulation (optimal).

The insight: at most 2 transactions means the state must track how many transactions have been completed (0, 1, or 2) alongside the holding status. A transaction is "buy + sell" pair; we count by sells. So states are: (0 transactions done, holding), (0 transactions done, not holding), (1 transaction done, holding), (1 transaction done, not holding), (2 transactions done, not holding). (Holding after 2 transactions is irrelevant - we'd never buy a third time.) The DP picks the best transition per day.

The Problem

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).

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.
Or: Buy on day 4 (price 0), sell on day 8 (price 4, profit 4); plus an earlier transaction.

Example 2:

Input:  prices = [1,2,3,4,5]
Output: 4

Example 3:

Input:  prices = [7,6,4,3,1]
Output: 0

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	6-variable rolling DP	O(n)	O(1)	Canonical
2	4-variable elegant formulation	O(n)	O(1)	Optimal

State variables (each updated per day):

buy1, sell1: max profit after first buy/sell.
buy2, sell2: max profit after second buy/sell.

Transitions per day:

buy1 = max(buy1, -prices[i]).
sell1 = max(sell1, buy1 + prices[i]).
buy2 = max(buy2, sell1 - prices[i]).
sell2 = max(sell2, buy2 + prices[i]).

Base: buy1 = buy2 = -INF, sell1 = sell2 = 0 (some variants initialize buy1 to -prices[0]; same effect). Answer: sell2.

Approach 1: 4-Variable Elegant Formulation - Optimal

The Idea

Track four key states: after-buy-1, after-sell-1, after-buy-2, after-sell-2. Each day, update them in forward order (buy1 first, then sell1, etc.). The "buy" states subtract the current price; the "sell" states add it. The transitions chain together: sell1 depends on buy1; buy2 depends on sell1; sell2 depends on buy2.

Logic Flowchart

graph TD
    A["buy1 = buy2 = -INF; sell1 = sell2 = 0"] --> B["for each price p:"]
    B --> C["buy1 = max(buy1, -p)"]
    C --> D["sell1 = max(sell1, buy1 + p)"]
    D --> E["buy2 = max(buy2, sell1 - p)"]
    E --> F["sell2 = max(sell2, buy2 + p)"]
    F --> B
    B --> G["return sell2"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the 4-variable Stock III DP: update each of buy1, sell1, buy2, sell2 in order, each based on the just-updated previous variable.

Code

public static int maxProfitIII(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;
    for (int p : prices) {
        buy1 = Math.max(buy1, -p);
        sell1 = Math.max(sell1, buy1 + p);
        buy2 = Math.max(buy2, sell1 - p);
        sell2 = Math.max(sell2, buy2 + p);
    }
    return sell2;
}

// Usage:
// maxProfitIII([3,3,5,0,0,3,1,4]) -> 6
// maxProfitIII([1,2,3,4,5]) -> 4
// maxProfitIII([7,6,4,3,1]) -> 0

This Java code computes max profit with at most two transactions via 4-variable rolling DP, updating each variable in forward order.

Step-by-Step Walkthrough

Tracing maxProfitIII([3,3,5,0,0,3,1,4]):

graph LR
    F0["init: buy1=-INF, sell1=0, buy2=-INF, sell2=0"]
    F1["after p=3: buy1=-3, sell1=0, buy2=-3, sell2=0"]
    F2["after some steps; p=0 (4th): buy1=0, sell1=2, buy2=0, sell2=2; after p=4 (last): buy1=0, sell1=4, buy2=3, sell2=6"]
    F3["return 6"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough computes max profit 6 with at most two transactions: the DP tracks both transaction completions through the price sequence.

Result: 6.

Complexity

Time: O(n). Space: O(1).

Complexity Comparison

Approach	Time	Space	Key Idea
4-variable elegant DP	O(n)	O(1)	track after-buy/sell-1 and after-buy/sell-2; update forward per day

The 4-variable formulation is the canonical and optimal solution. Each variable represents "the best so far" for a specific stage of the at-most-2-transaction process.

Variations & Follow-ups

Why is forward update order correct?

When updating each day:

buy1 reads the previous buy1 (no other dependency).
sell1 reads the current (just-updated) buy1.
buy2 reads the current (just-updated) sell1.
sell2 reads the current (just-updated) buy2.

This chained dependency is fine because each "current" read represents "best after considering today's action." It's a valid Markov-step: the new state at each level reads the best state at the previous level after also considering today. The general lesson: DPs with chained variables can update in forward order when each step's read represents the best-considering-today version. Verify the dependency chain matches the desired semantics.

How does this generalize to K transactions?

For at most K transactions, maintain 2K variables: buy1, sell1, ..., buyK, sellK. Update each per day, in forward order. Time: O(n · K), space: O(K). For K small (≤ 100), this is fast. For K very large (≥ n/2), the answer reduces to the unrestricted case (Stock II), which is O(n) with a 2-variable DP. The next topic (30.91) handles the general K case.

How does this compare to a divide-and-conquer approach?

A natural alternative: find the best split point i such that bestProfit(prices[0..i]) + bestProfit(prices[i..n-1]) is maximized, with each sub-array allowed one transaction. This requires precomputing left-side and right-side max profits, then combining - O(n) time, O(n) space. The 4-variable DP is more elegant but conceptually equivalent. The general lesson: bounded-transaction problems often admit both rolling-variable and split-point formulations. The choice depends on whether you want the DP to be "online" (rolling) or "offline" (split-point).

What about edge cases?

n = 1: No transactions possible; profit 0.
Monotonically decreasing prices: Profit 0.
One large profit opportunity: Use just one transaction (the DP automatically chooses the best 1 or 2).
K = 0 implicit (zero transactions): Profit 0 - but the problem's "at most 2" includes the option to do 0.

Common Interview Pitfalls

Wrong update order. buy1 must be updated before sell1 (which reads buy1). Reverse order gives wrong answers.
Treating "at most 2" as "exactly 2." The DP automatically handles "fewer than 2" by keeping sell2 = sell1 (or 0) when the second transaction isn't profitable.
Confusing buy/sell semantics. Buy = "currently holding"; sell = "currently not holding." Reading the wrong variable at the end (e.g., buy2 instead of sell2) gives nonsensical results.
Initialization to 0 for buy1. Should be -INF (or -prices[0]) - buy1 is the cost of buying, which is negative.

Why This Topic Matters

Best Time to Buy and Sell Stock III demonstrates bounded-transaction State Machine DP: the at-most-K constraint adds a transaction-count dimension to the state. The 4-variable rolling DP is elegant and O(1) space. The chained forward-update pattern (each variable reads the just-updated previous one) is a useful trick across DP problems with cascading dependencies.

The next and final topic, Best Time to Buy and Sell Stock IV, generalizes to at most K transactions. State = (position, transactions used, holding), total 2 · K + 1 states. The naive DP is O(n · K · 2); the rolling-variable formulation drops space to O(K). For K ≥ n/2, the problem degenerates to the unrestricted case (Stock II) with O(n) and O(1) space. It demonstrates general parametric State Machine DP and shows that parametric problems gracefully degenerate to simpler cases when the parameter is large. It closes Module 30.

Back to DSA Mastery - Interview Prep, End to End