Best Time to Buy and Sell Stock III

LeetCode 123: Best Time to Buy and Sell Stock III Solution & Explanation

Problem Overview

TL;DR: We solve this by modeling the problem as a finite state machine with four variables tracking the maximum profit for the first buy, first sell, second buy, and second sell respectively.

The Best Time to Buy and Sell Stock III problem asks us to find the maximum profit obtainable from a series of stock prices given a specific constraint: we can complete at most two transactions. A transaction consists of buying and then selling. Importantly, we cannot engage in multiple transactions simultaneously; we must sell our current holding before buying again.

This is a popular interview question because it evolves the simple "buy low, sell high" logic into a multi-stage decision process. The LeetCode 123 solution requires handling dependencies between the first and second transactions efficiently.

Brute Force Approach for Best Time to Buy and Sell Stock III

A naive approach attempts to divide the problem into two independent single-transaction problems. Since we can make at most two transactions, there must be a dividing point $i$ in the array where the first transaction happens on or before day $i$, and the second transaction happens after day $i$.

The algorithm would look like this:

1. Iterate through every possible split point $i$ from $0$ to $n$.
2. For each $i$, calculate the maximum profit for one transaction in the subarray prices[0...i].
3. Calculate the maximum profit for one transaction in the subarray prices[i...n-1].
4. Sum these two profits.
5. Track the maximum sum found across all split points.

Pseudo-code:

max_total_profit = 0
for i from 0 to length(prices):
    left_profit = max_profit_1_trans(prices[0...i])
    right_profit = max_profit_1_trans(prices[i...length])
    max_total_profit = max(max_total_profit, left_profit + right_profit)
return max_total_profit

Complexity Analysis: The time complexity is $O(N^2)$. Calculating the maximum profit for a subarray takes $O(N)$ time. Since we repeat this calculation for every possible split point $i$ (where there are $N$ split points), the total operations are proportional to $N^2$.

Why it fails: With constraints where prices.length can be up to $10^5$, an $O(N^2)$ solution requires roughly $10^{10}$ operations. This far exceeds the typical limit of $10^8$ operations per second, resulting in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Dynamic Programming (DP) Patterns

We utilize the Dynamic Programming pattern by maintaining four variables representing the maximum profit (or best balance) achievable for each of the four states described above.

Variables to Maintain:

1. t1_cost: The lowest price paid for the first stock so far. (Alternatively, the max balance after the first buy, which is negative price).
2. t1_profit: The maximum profit after the first sell.
3. t2_cost: The lowest effective price paid for the second stock. We calculate this as price - t1_profit. This effectively reinvests our first profit to lower the cost of the second buy.
4. t2_profit: The maximum total profit after the second sell.

Constraints Enforced:

• We update these variables sequentially for each price in the array.
• The order of updates matters to simulate the timeline correctly (though since we can buy and sell on the same day, updating in a single pass works).
• t1_profit depends on t1_cost.
• t2_cost depends on t1_profit.
• t2_profit depends on t2_cost.

By the end of the iteration, t2_profit will hold the maximum profit for two transactions. If only one transaction was optimal, the math naturally carries the single transaction profit through to t2_profit.

Execution Flow

1. Initialize Variables:

   • t1_cost: Infinity (or prices[0]) representing the min cost to buy stock 1.
   • t1_profit: 0.
   • t2_cost: Infinity (or prices[0]) representing the min cost to buy stock 2 (factoring in previous profit).
   • t2_profit: 0.

2. Iterate through each price in prices:

   • Step 2a: Update t1_cost. It is the minimum of the current t1_cost and the current price.
   • Step 2b: Update t1_profit. It is the maximum of the current t1_profit and price - t1_cost.
   • Step 2c: Update t2_cost. It is the minimum of the current t2_cost and price - t1_profit. (Think of this as: "What is the price of the second stock, heavily discounted by the money we made in the first trade?").
   • Step 2d: Update t2_profit. It is the maximum of the current t2_profit and price - t2_cost.

3. Return t2_profit.

Proof of Correctness

The correctness relies on the optimal substructure property of Dynamic Programming.

• t1_profit at step $i$ correctly stores the max profit for 1 transaction using prices up to day $i$.
• t2_cost uses t1_profit. By minimizing price - t1_profit, we are mathematically equivalent to maximizing t1_profit - price. This represents the best state of our wallet after buying the second stock.
• t2_profit maximizes price - t2_cost. Substituting t2_cost, we are maximizing price_sell2 - (price_buy2 - profit_trans1), which simplifies to profit_trans1 + (price_sell2 - price_buy2).
• Therefore, t2_profit always accumulates the maximum sum of profits from two non-overlapping transactions.

Pattern Reuse Notes

The DP - Stock problems pattern used here is directly applicable to several other LeetCode problems. Mastering the state machine approach allows you to solve variations by simply adjusting the state transitions.

• LeetCode 121: Best Time to Buy and Sell Stock: This is the base case ($k=1$). It is equivalent to calculating just t1_profit.
• LeetCode 122: Best Time to Buy and Sell Stock II: This allows infinite transactions ($k=\infty$). The greedy approach works here, but it can also be modeled as a state machine where the "sell" state loops back to the "buy" state.
• LeetCode 188: Best Time to Buy and Sell Stock IV: This is the generalized version of Problem 123 where $k$ is an input. You simply use arrays of size $k$ instead of 4 individual variables.
• LeetCode 309: Best Time to Buy and Sell Stock with Cooldown: This introduces a "Cooldown" state. The pattern is identical, but the state diagram adds a mandatory rest node between selling and buying again.

Reference Implementation

C++ Solution for LeetCode 123

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    int maxProfit(std::vector<int>& prices) {
8        // Initialize costs to max integer to ensure the first price is picked up
9        int t1_cost = INT_MAX;
10        int t2_cost = INT_MAX;
11        
12        // Profits start at 0
13        int t1_profit = 0;
14        int t2_profit = 0;
15
16        for (int price : prices) {
17            // Minimize cost for first buy
18            t1_cost = std::min(t1_cost, price);
19            
20            // Maximize profit for first sell
21            t1_profit = std::max(t1_profit, price - t1_cost);
22            
23            // Minimize effective cost for second buy (price - previous profit)
24            t2_cost = std::min(t2_cost, price - t1_profit);
25            
26            // Maximize profit for second sell
27            t2_profit = std::max(t2_profit, price - t2_cost);
28        }
29
30        return t2_profit;
31    }
32};

Java Solution for LeetCode 123

1class Solution {
2    public int maxProfit(int[] prices) {
3        // Initialize costs to MAX_VALUE to serve as the baseline for minimization
4        int t1Cost = Integer.MAX_VALUE;
5        int t2Cost = Integer.MAX_VALUE;
6        
7        // Profits are initially 0
8        int t1Profit = 0;
9        int t2Profit = 0;
10
11        for (int price : prices) {
12            // 1. Buy 1: Minimize the cost of the first stock
13            t1Cost = Math.min(t1Cost, price);
14            
15            // 2. Sell 1: Maximize profit from the first transaction
16            t1Profit = Math.max(t1Profit, price - t1Cost);
17            
18            // 3. Buy 2: Minimize the effective cost of the second stock
19            // Effect: We reinvest t1Profit into this purchase
20            t2Cost = Math.min(t2Cost, price - t1Profit);
21            
22            // 4. Sell 2: Maximize total profit from two transactions
23            t2Profit = Math.max(t2Profit, price - t2Cost);
24        }
25
26        return t2Profit;
27    }
28}

Python Solution for LeetCode 123

1class Solution:
2    def maxProfit(self, prices: list[int]) -> int:
3        # Initialize costs to infinity
4        t1_cost = float('inf')
5        t2_cost = float('inf')
6        
7        # Initialize profits to 0
8        t1_profit = 0
9        t2_profit = 0
10        
11        for price in prices:
12            # First transaction: Buy
13            t1_cost = min(t1_cost, price)
14            
15            # First transaction: Sell
16            t1_profit = max(t1_profit, price - t1_cost)
17            
18            # Second transaction: Buy (reinvesting profit)
19            t2_cost = min(t2_cost, price - t1_profit)
20            
21            # Second transaction: Sell
22            t2_profit = max(t2_profit, price - t2_cost)
23            
24        return t2_profit