Best Time to Buy and Sell Stock III

• Difficulty: Hard
• Topics: Array, Dynamic Programming
• Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the ith 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) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

Solution

Best Time to Buy and Sell Stock III

1. Problem Deconstruction (500+ words)

Rewrite the Problem

1. Technical Version

Given an integer array prices of length n where each element represents the daily stock price, determine the maximum achievable profit by executing at most two non-overlapping transactions. A transaction consists of buying on day i and selling on day j with i < j. Profit per transaction is prices[j] - prices[i]. Multiple transactions may not overlap: you cannot hold more than one share at any time, meaning a sell must occur before any subsequent buy. The goal is to maximize the sum of profits from zero, one, or two such transactions.

2. Beginner Version

Imagine you have a crystal ball showing future daily stock prices. You can buy and sell the stock at most twice, but you can only own one share at a time. You must sell any share you buy before buying again. Your objective is to maximize your total profit from these buy-sell cycles.

3. Mathematical Version

Let prices be a sequence [p_0, p_1, ..., p_{n-1}]. Define a transaction as a pair (i, j) with 0 ≤ i < j < n yielding profit p_j - p_i. We seek:

$$\max \left\{0,\ \max_{i<j} (p_j - p_i),\ \max_{\substack{i_1 < j_1 < i_2 < j_2}} \left( (p_{j_1} - p_{i_1}) + (p_{j_2} - p_{i_2}) \right) \right\}$$

where the inner maximums are taken over valid indices. This captures zero, one, or two transactions.

Constraint Analysis

• 1 <= prices.length <= 10^5
  This eliminates any O(n²) or worse algorithms. Solutions must be O(n log n) or ideally O(n). Large n also demands memory efficiency; O(n) extra space may be acceptable but O(1) is preferable.

• 0 <= prices[i] <= 10^5
  Prices are non-negative integers. Zero is allowed, meaning buying at zero is possible and selling at zero yields no profit. The maximum single-transaction profit is bounded by 10^5, so total profit fits within 32-bit integers. Hidden edge cases:

  1. All prices equal: maximum profit is zero.
  2. Strictly increasing: one transaction from first to last day maximizes profit; splitting reduces profit.
  3. Strictly decreasing: no profitable transaction.
  4. Large fluctuations: two transactions may outperform one.
  5. Very large arrays: algorithms must be cache‑friendly to avoid performance degradation.

2. Intuition Scaffolding

Generate 3 Analogies

1. Real‑World Metaphor (Ticket Resale)
   You are a concert ticket reseller with perfect knowledge of daily price fluctuations. You can complete at most two resale cycles: buy a ticket, then sell it later. You cannot hold two tickets simultaneously. Your goal is to maximize total profit by choosing the best days to buy and sell each time.

2. Gaming Analogy (RPG Potion Market)
   In a role‑playing game, you can buy and sell a rare potion daily. The price changes each day. You are limited to two complete buy‑sell cycles. You start with enough gold to buy once. Plan your purchases and sales to maximize your final gold, knowing you can only carry one potion at a time.

3. Math Analogy (Non‑overlapping Intervals)
   Given a sequence of numbers, find two non‑overlapping intervals [i, j] and [k, l] with i < j < k < l that maximize the sum of slopes (p_j - p_i) + (p_l - p_k). This is equivalent to partitioning the sequence into two segments and taking the maximum single‑transaction profit in each, but the partition point can vary.

Common Pitfalls Section

1. Taking the two largest individual profits without checking overlap
   Example: [1,5,0,6]. Largest profit is 6 (buy at 0, sell at 6), leaving no room for a second transaction. The correct two transactions are buy at 1 sell at 5 (4) and buy at 0 sell at 6 (6), but they overlap, so they cannot both be taken.

2. Assuming exactly two transactions are required
   The problem says “at most two.” In a strictly increasing array, one transaction yields higher profit than any two non‑overlapping transactions.

3. Allowing same‑day buy‑sell
   While not explicitly forbidden, the requirement “sell before buy again” implies buy_day < sell_day. Same‑day transactions would yield zero profit and are irrelevant for maximization.

4. Greedy on local minima and maxima
   For one transaction, tracking the global minimum works. For two, greedily taking the best transaction and then the best in the remaining days may fail due to overlap.

5. Ignoring the zero‑transaction case
   If all profits are negative (i.e., prices are non‑increasing), the best is to do nothing, yielding zero profit.

3. Approach Encyclopedia

Approach 1: Brute Force (O(n⁴))

Enumerate all possible sets of up to two transactions.

Pseudocode:

max_profit = 0
# Zero or one transaction
for i in range(n):
    for j in range(i+1, n):
        max_profit = max(max_profit, prices[j] - prices[i])
# Two transactions
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            for l in range(k+1, n):
                profit = (prices[j] - prices[i]) + (prices[l] - prices[k])
                max_profit = max(max_profit, profit)
return max_profit

Complexity Proof:
Four nested loops each up to n ⇒ O(n⁴) time. Space O(1).

Visualization:

Days:   0  1  2  3  4  5  6  7
Prices: 3  3  5  0  0  3  1  4
        i  j        k     l    → profit = (5-3)+(4-1)=5

Approach 2: Split Array (O(n²))

For each split index i, compute max profit in prices[0..i] and prices[i+1..n-1].

Pseudocode:

def one_transaction_profit(arr):
    min_price = inf
    max_profit = 0
    for price in arr:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

max_profit = 0
for i in range(n):
    left = prices[:i+1]
    right = prices[i+1:]
    max_profit = max(max_profit, 
                     one_transaction_profit(left) + 
                     one_transaction_profit(right))
return max_profit

Complexity Proof:
one_transaction_profit is O(k) for length k. Called for each split ⇒ O(n²) time. Space O(1) aside from slicing.

Visualization:

Split at i=3:
Left:  [3,3,5,0] → best: buy 3 sell 5 → profit 2
Right: [0,3,1,4] → best: buy 0 sell 4 → profit 4
Total = 6

Approach 3: Precomputed Left/Right DP (O(n))

Precompute left[i] = max profit with one transaction in prices[0..i], and right[i] = max profit with one transaction in prices[i..n-1].

Pseudocode:

n = len(prices)
left = [0]*n
min_price = prices[0]
for i in range(1, n):
    left[i] = max(left[i-1], prices[i] - min_price)
    min_price = min(min_price, prices[i])

right = [0]*n
max_price = prices[-1]
for i in range(n-2, -1, -1):
    right[i] = max(right[i+1], max_price - prices[i])
    max_price = max(max_price, prices[i])

max_profit = 0
for i in range(n-1):
    max_profit = max(max_profit, left[i] + right[i+1])
max_profit = max(max_profit, left[-1])  # one transaction
return max_profit

Complexity Proof:
Three linear passes ⇒ O(n) time. Two arrays of size n ⇒ O(n) space.

Visualization:

Index:   0  1  2  3  4  5  6  7
Prices:  3  3  5  0  0  3  1  4
Left:    0  0  2  2  2  3  3  4
Right:   4  4  4  4  4  3  3  0
Split at i=3: left[3]=2, right[4]=4 → total 6.

Approach 4: State Machine DP (O(n), O(1))

Model states after first buy (hold1), first sell (sold1), second buy (hold2), second sell (sold2).

Pseudocode:

hold1 = -inf  # after buying first stock
sold1 = 0     # after selling first stock
hold2 = -inf  # after buying second stock
sold2 = 0     # after selling second stock

for price in prices:
    sold2 = max(sold2, hold2 + price)
    hold2 = max(hold2, sold1 - price)
    sold1 = max(sold1, hold1 + price)
    hold1 = max(hold1, -price)

return max(sold1, sold2)

Complexity Proof:
Single pass, constant‑time updates ⇒ O(n) time. Four variables ⇒ O(1) space.

Visualization:

Day:  Price  hold1  sold1  hold2  sold2
0     3      -3     0      -3     0
1     3      -3     0      -3     0
2     5      -3     2      -3     2
3     0       0     2       2     2
4     0       0     2       2     2
5     3       0     3       2     5
6     1       0     3       2     5
7     4       0     4       2     6  → answer = max(4,6)=6

4. Code Deep Dive

Line‑by‑Line Annotations (State Machine DP)

def maxProfit(prices):
    """
    Compute maximum profit with at most two transactions.
    
    Args:
        prices: List[int] - Daily stock prices.
    
    Returns:
        int - Maximum achievable profit.
    """
    # State variables initialized to represent impossible or neutral states.
    hold1 = float('-inf')  # Profit after first buy. -∞ because no purchase yet.
    sold1 = 0              # Profit after first sale. Zero if no transaction.
    hold2 = float('-inf')  # Profit after second buy.
    sold2 = 0              # Profit after second sale.
    
    for price in prices:
        # Update in reverse order to avoid using today's updated values prematurely.
        sold2 = max(sold2, hold2 + price)   # Sell second stock today.
        hold2 = max(hold2, sold1 - price)   # Buy second stock today.
        sold1 = max(sold1, hold1 + price)   # Sell first stock today.
        hold1 = max(hold1, -price)          # Buy first stock today.
    
    # The answer is the better of at most two transactions.
    return max(sold1, sold2)

Edge Case Handling

• Example 1 ([3,3,5,0,0,3,1,4])
  The algorithm captures the two transactions: buy at 0 (day 3), sell at 3 (day 5); buy at 1 (day 6), sell at 4 (day 7). The reverse update order ensures that sold2 uses the previous day’s hold2.

• Example 2 ([1,2,3,4,5])
  Strictly increasing: sold1 ends at 4 (buy at 1, sell at 5). sold2 also reaches 4 via two transactions (e.g., buy at 1 sell at 2 and buy at 2 sell at 5, but same‑day sell‑buy not allowed). The state machine correctly yields 4.

• Example 3 ([7,6,4,3,1])
  Decreasing prices: all profits remain zero, returning 0.

• Single Day ([5])
  hold1 becomes -5, sold1 stays 0, hold2 becomes -5, sold2 stays 0 ⇒ returns 0.

• All Zeros ([0,0,0])
  hold1 becomes 0, sold1 stays 0, hold2 stays 0, sold2 stays 0 ⇒ returns 0.

5. Complexity War Room

Hardware‑Aware Analysis

• Time: O(n) with n ≤ 10⁵. On a modern CPU (∼10⁹ ops/sec), 10⁵ iterations take < 1 ms.
• Space: O(1) extra memory. The input array (∼400 KB for 10⁵ integers) fits in L3 cache, ensuring cache‑friendly access.
• Memory bandwidth: Single sequential pass minimizes cache misses.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force (quadruple loops)	O(n⁴)	O(1)	High	❌ Fails large n
Split Array (O(n²))	O(n²)	O(1)	Medium	❌ Too slow for n=10⁵
Precomputed DP (left/right)	O(n)	O(n)	High	✅ Acceptable, extra space
State Machine DP	O(n)	O(1)	Medium	✅ Optimal, preferred
Generalized DP for k transactions	O(kn)	O(k)	Medium	✅ Good for follow‑up

6. Pro Mode Extras

Variants Section

1. One Transaction (LeetCode 121)
   Track global minimum and maximum profit:

   min_price = inf; profit = 0
   for p in prices: min_price = min(min_price, p); profit = max(profit, p - min_price)
   

2. Unlimited Transactions (LeetCode 122)
   Sum all positive daily differences:

   total = 0
   for i in range(1, len(prices)):
       if prices[i] > prices[i-1]:
           total += prices[i] - prices[i-1]
   

3. At Most k Transactions (LeetCode 188)
   Extend state machine to k pairs:

   hold = [-inf] * (k+1); sold = [0] * (k+1)
   for price in prices:
       for j in range(k, 0, -1):
           sold[j] = max(sold[j], hold[j] + price)
           hold[j] = max(hold[j], sold[j-1] - price)
   return max(sold)
   

4. With Cooldown (LeetCode 309)
   Add a cooldown state representing the day after a sell.

5. With Transaction Fee (LeetCode 714)
   Subtract fee when selling (or when buying).

Interview Cheat Sheet

• Clarify: Confirm “at most two transactions” and that buy‑sell pairs must be strictly ordered.
• Brute Force Mention: Show awareness of naive solutions but highlight inefficiency.
• Optimize Stepwise: Propose split‑array DP, then state machine as final optimization.
• Walk Through Example: Use a small example to demonstrate state transitions.
• Edge Cases: Mention zero‑profit, single day, increasing/decreasing sequences.
• Complexity: Always state time and space complexity clearly.
• Follow‑up: Be prepared to extend to k transactions or other constraints.

Final Tip: In interviews, always think aloud and justify each design decision. The state machine solution is both time‑ and space‑optimal, making it the gold standard for this problem.