Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Best Time to Buy and Sell Stock III

HARDProblemSolveExternal Links

Description

You are given an array prices where prices[i] represents the price of a given stock on the i-th day.

Find the maximum profit you can achieve by completing at most two transactions (a transaction is one buy followed by one sell).

You may not hold more than one share of the stock at any time — you must sell your current stock before purchasing again. If no profit can be made, return 0.

Examples

Example 1

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

Output: 6

Explanation: The best strategy uses two transactions. First, buy on day 4 (price = 0) and sell on day 6 (price = 3), earning a profit of 3. Then, buy on day 7 (price = 1) and sell on day 8 (price = 4), earning a profit of 3. The total profit is 3 + 3 = 6.

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). This single transaction yields a profit of 4. Using two transactions would not improve the result because the prices increase monotonically — any split into two transactions would sum to the same total gain.

Example 3

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

Output: 0

Explanation: Prices only decrease every day. No transaction can produce a positive profit, so the best choice is to not trade at all and return 0.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to solve this is to recognize that with at most two transactions, we can split the price array into two halves at every possible dividing point. For each split, we compute the maximum profit from one transaction on the left portion and one transaction on the right portion, then combine them.

Think of it like drawing a vertical line through a timeline of stock prices. Everything to the left of the line is your first opportunity to trade, and everything to the right is your second opportunity. By sliding this dividing line across every day, you consider all possible ways to partition your two trades.

For each half, finding the best single-transaction profit is a classic problem: track the minimum price seen so far, and at each day compute the difference between the current price and that minimum.

Step-by-Step Explanation

Let's trace through with prices = [3, 3, 5, 0, 0, 3, 1, 4]:

Step 1: Try split at day 0. Left portion = [3], right portion = [3, 5, 0, 0, 3, 1, 4].

  • Left max profit = 0 (single element, no transaction possible)
  • Right max profit = 4 (buy at 0, sell at 4)
  • Total = 0 + 4 = 4

Step 2: Try split at day 1. Left = [3, 3], right = [5, 0, 0, 3, 1, 4].

  • Left max profit = 0 (no price increase)
  • Right max profit = 4 (buy at 0, sell at 4)
  • Total = 0 + 4 = 4

Step 3: Try split at day 2. Left = [3, 3, 5], right = [0, 0, 3, 1, 4].

  • Left max profit = 2 (buy at 3, sell at 5)
  • Right max profit = 4 (buy at 0, sell at 4)
  • Total = 2 + 4 = 6

Step 4: Try split at day 3. Left = [3, 3, 5, 0], right = [0, 3, 1, 4].

  • Left max profit = 2 (buy at 3, sell at 5)
  • Right max profit = 4 (buy at 0, sell at 4)
  • Total = 2 + 4 = 6

Step 5: Try split at day 4. Left = [3, 3, 5, 0, 0], right = [3, 1, 4].

  • Left max profit = 2 (buy at 3, sell at 5)
  • Right max profit = 3 (buy at 1, sell at 4)
  • Total = 2 + 3 = 5

Step 6: Continue splits... The maximum across all splits is 6.

Result: Maximum profit = 6

Brute Force — Splitting Array at Every Day — Watch how we try every possible split point to divide the array into two halves, computing the best single-transaction profit for each half and combining them.

Algorithm

  1. For each split point i from 0 to n-1:
    a. Compute the maximum profit achievable from a single transaction in prices[0..i] by tracking the minimum price and maximum difference
    b. Compute the maximum profit achievable from a single transaction in prices[i+1..n-1] by tracking the maximum price from the right and maximum difference
    c. Record total = left_profit + right_profit
  2. Return the maximum total across all split points

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            // Max profit from one transaction in prices[0..i]
            int leftProfit = 0;
            int minPrice = prices[0];
            for (int j = 1; j <= i; j++) {
                minPrice = min(minPrice, prices[j]);
                leftProfit = max(leftProfit, prices[j] - minPrice);
            }
            
            // Max profit from one transaction in prices[i+1..n-1]
            int rightProfit = 0;
            int maxPrice = 0;
            for (int j = n - 1; j > i; j--) {
                maxPrice = max(maxPrice, prices[j]);
                rightProfit = max(rightProfit, maxPrice - prices[j]);
            }
            
            result = max(result, leftProfit + rightProfit);
        }
        
        return result;
    }
};
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        result = 0
        
        for i in range(n):
            # Max profit from one transaction in prices[0..i]
            left_profit = 0
            min_price = prices[0]
            for j in range(1, i + 1):
                min_price = min(min_price, prices[j])
                left_profit = max(left_profit, prices[j] - min_price)
            
            # Max profit from one transaction in prices[i+1..n-1]
            right_profit = 0
            max_price = 0
            for j in range(n - 1, i, -1):
                max_price = max(max_price, prices[j])
                right_profit = max(right_profit, max_price - prices[j])
            
            result = max(result, left_profit + right_profit)
        
        return result
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            // Max profit from one transaction in prices[0..i]
            int leftProfit = 0;
            int minPrice = prices[0];
            for (int j = 1; j <= i; j++) {
                minPrice = Math.min(minPrice, prices[j]);
                leftProfit = Math.max(leftProfit, prices[j] - minPrice);
            }
            
            // Max profit from one transaction in prices[i+1..n-1]
            int rightProfit = 0;
            int maxPrice = 0;
            for (int j = n - 1; j > i; j--) {
                maxPrice = Math.max(maxPrice, prices[j]);
                rightProfit = Math.max(rightProfit, maxPrice - prices[j]);
            }
            
            result = Math.max(result, leftProfit + rightProfit);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n possible split points, we scan the left portion (up to n elements) and the right portion (up to n elements) to find the best single-transaction profit. This gives us n iterations of O(n) work each, resulting in O(n²) total.

Space Complexity: O(1)

We only use a constant number of variables — the split point index, min/max trackers, and profit accumulators. No additional arrays or data structures are allocated.

Why This Approach Is Not Efficient

The brute force approach runs in O(n²) time. With n up to 10^5, that means up to 10^10 operations — far too slow for typical time limits of 1–2 seconds.

The core inefficiency is redundant computation: for each split point, we recalculate the best single-transaction profit from scratch by scanning the left and right subarrays. Moving the split point by one day changes very little about these subarrays, yet we redo all the work.

Key insight: We can precompute the best single-transaction profit ending at or before each day (a prefix array) and the best single-transaction profit starting at or after each day (a suffix array) in a single O(n) pass each. Then, combining them for every split point becomes O(1) per split, reducing total time to O(n).

Better Approach - Prefix and Suffix Profit Arrays

Intuition

Instead of recalculating from scratch at each split point, we precompute two helper arrays:

  1. prefix[i] — the maximum profit from one transaction using only days 0 through i. We build this left-to-right by tracking the minimum price seen so far.
  2. suffix[i] — the maximum profit from one transaction using only days i through n-1. We build this right-to-left by tracking the maximum price seen so far.

Once we have both arrays, the answer is simply the maximum of prefix[i] + suffix[i+1] across all valid split points. Each lookup is O(1), so the combination step is O(n).

Imagine you already know the best trade you could have made in the morning and the best trade you could have made in the afternoon. You don't need to re-examine every morning transaction when you shift the boundary by one hour — you just look up the precomputed answer.

Step-by-Step Explanation

Let's trace through with prices = [3, 3, 5, 0, 0, 3, 1, 4]:

Step 1: Build prefix array (left-to-right)

  • Day 0: min_price = 3, prefix[0] = 0 (can't sell on the same day we start)
  • Day 1: min_price = 3, prices[1]-3 = 0, prefix[1] = max(0, 0) = 0
  • Day 2: min_price = 3, prices[2]-3 = 2, prefix[2] = max(0, 2) = 2
  • Day 3: min_price = 0, prices[3]-0 = 0, prefix[3] = max(2, 0) = 2
  • Day 4: min_price = 0, prices[4]-0 = 0, prefix[4] = max(2, 0) = 2
  • Day 5: min_price = 0, prices[5]-0 = 3, prefix[5] = max(2, 3) = 3
  • Day 6: min_price = 0, prices[6]-0 = 1, prefix[6] = max(3, 1) = 3
  • Day 7: min_price = 0, prices[7]-0 = 4, prefix[7] = max(3, 4) = 4
  • prefix = [0, 0, 2, 2, 2, 3, 3, 4]

Step 2: Build suffix array (right-to-left)

  • Day 7: max_price = 4, suffix[7] = 0
  • Day 6: max_price = 4, 4-1 = 3, suffix[6] = max(0, 3) = 3
  • Day 5: max_price = 4, 4-3 = 1, suffix[5] = max(3, 1) = 3
  • Day 4: max_price = 4, 4-0 = 4, suffix[4] = max(3, 4) = 4
  • Day 3: max_price = 4, 4-0 = 4, suffix[3] = max(4, 4) = 4
  • Day 2: max_price = 4, 4-5 = -1, suffix[2] = max(4, -1) = 4
  • Day 1: max_price = 5, 5-3 = 2, suffix[1] = max(4, 2) = 4
  • Day 0: max_price = 5, 5-3 = 2, suffix[0] = max(4, 2) = 4
  • suffix = [4, 4, 4, 4, 4, 3, 3, 0]

Step 3: Combine prefix and suffix

  • i=0: prefix[0] + suffix[1] = 0 + 4 = 4
  • i=1: prefix[1] + suffix[2] = 0 + 4 = 4
  • i=2: prefix[2] + suffix[3] = 2 + 4 = 6 ← maximum!
  • i=3: prefix[3] + suffix[4] = 2 + 4 = 6 ← tied
  • i=4: prefix[4] + suffix[5] = 2 + 3 = 5
  • i=5: prefix[5] + suffix[6] = 3 + 3 = 6 ← tied
  • Also consider single transaction: prefix[7] = 4

Result: Maximum profit = 6

Prefix-Suffix Approach — Precompute and Combine — Watch how we build a prefix array of best left-side profits and a suffix array of best right-side profits, then combine them to find the optimal two-transaction split.

Algorithm

  1. Create a prefix array of size n:
    • Traverse left-to-right, tracking the minimum price seen so far
    • prefix[i] = max profit from one transaction using days 0 to i
  2. Create a suffix array of size n:
    • Traverse right-to-left, tracking the maximum price seen so far
    • suffix[i] = max profit from one transaction using days i to n-1
  3. Iterate over all split points i from 0 to n-2:
    • Compute prefix[i] + suffix[i+1]
    • Track the maximum
  4. Also consider prefix[n-1] (only one transaction)
  5. Return the maximum value found

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        
        // prefix[i] = max profit from one transaction in prices[0..i]
        vector<int> prefix(n, 0);
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = min(minPrice, prices[i]);
            prefix[i] = max(prefix[i - 1], prices[i] - minPrice);
        }
        
        // suffix[i] = max profit from one transaction in prices[i..n-1]
        vector<int> suffix(n, 0);
        int maxPrice = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxPrice = max(maxPrice, prices[i]);
            suffix[i] = max(suffix[i + 1], maxPrice - prices[i]);
        }
        
        // Combine: try every split point
        int result = 0;
        for (int i = 0; i < n; i++) {
            int secondProfit = (i + 1 < n) ? suffix[i + 1] : 0;
            result = max(result, prefix[i] + secondProfit);
        }
        
        return result;
    }
};
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        # prefix[i] = max profit from one transaction in prices[0..i]
        prefix = [0] * n
        min_price = prices[0]
        for i in range(1, n):
            min_price = min(min_price, prices[i])
            prefix[i] = max(prefix[i - 1], prices[i] - min_price)
        
        # suffix[i] = max profit from one transaction in prices[i..n-1]
        suffix = [0] * n
        max_price = prices[n - 1]
        for i in range(n - 2, -1, -1):
            max_price = max(max_price, prices[i])
            suffix[i] = max(suffix[i + 1], max_price - prices[i])
        
        # Combine: try every split point
        result = 0
        for i in range(n):
            second_profit = suffix[i + 1] if i + 1 < n else 0
            result = max(result, prefix[i] + second_profit)
        
        return result
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        
        // prefix[i] = max profit from one transaction in prices[0..i]
        int[] prefix = new int[n];
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            prefix[i] = Math.max(prefix[i - 1], prices[i] - minPrice);
        }
        
        // suffix[i] = max profit from one transaction in prices[i..n-1]
        int[] suffix = new int[n];
        int maxPrice = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxPrice = Math.max(maxPrice, prices[i]);
            suffix[i] = Math.max(suffix[i + 1], maxPrice - prices[i]);
        }
        
        // Combine: try every split point
        int result = 0;
        for (int i = 0; i < n; i++) {
            int secondProfit = (i + 1 < n) ? suffix[i + 1] : 0;
            result = Math.max(result, prefix[i] + secondProfit);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make three linear passes over the array: one to build the prefix array, one to build the suffix array, and one to combine them. Each pass is O(n), so total time is O(3n) = O(n).

Space Complexity: O(n)

We allocate two auxiliary arrays of size n — the prefix array and the suffix array. This is the dominant space usage.

Why This Approach Is Not Efficient

The prefix-suffix approach runs in O(n) time, which is already optimal. However, its space complexity is O(n) due to the two auxiliary arrays. For n up to 10^5, this is acceptable, but we can do better.

The key observation is that we don't actually need to store all prefix and suffix values. Instead, we can model the problem as a state machine where we track the profit at each of four stages: after the first buy, after the first sell, after the second buy, and after the second sell. By updating these four values in a single forward pass, we reduce space to O(1) while keeping time at O(n).

Optimal Approach - State Machine DP

Intuition

Rather than thinking about split points or arrays, imagine you are walking through the timeline of prices and at each moment you are in one of four possible trading states:

  1. After first buy (firstBuy): You have purchased the first stock but not sold it. The profit at this stage is negative (you spent money).
  2. After first sell (firstSell): You completed your first trade and pocketed the profit.
  3. After second buy (secondBuy): Using your profit from the first trade, you purchased a second stock.
  4. After second sell (secondSell): You sold the second stock and realized the combined profit from both trades.

At each day, for each state, you make a choice: either stay in the current state (skip this day) or transition to this state (by buying or selling at today's price). You always pick the option that maximizes your profit.

The beauty of this approach is that these four variables capture all the information we need. We don't need to know which specific days we traded — just the best profit achievable at each stage so far. After processing all days, secondSell holds the answer.

Step-by-Step Explanation

Let's trace through with prices = [3, 3, 5, 0, 0, 3, 1, 4]:

Step 1: Initialize on day 0 (price = 3)

  • firstBuy = -3 (bought at price 3)
  • firstSell = 0 (no sale yet)
  • secondBuy = -3 (hypothetical: zero-profit first trade, then buy at 3)
  • secondSell = 0 (no second sale yet)

Step 2: Day 1 (price = 3)

  • firstBuy = max(-3, -3) = -3 (buying at 3 is same cost)
  • firstSell = max(0, -3+3) = 0 (selling gives 0 profit)
  • secondBuy = max(-3, 0-3) = -3 (no improvement)
  • secondSell = max(0, -3+3) = 0 (no improvement)

Step 3: Day 2 (price = 5)

  • firstBuy = max(-3, -5) = -3 (keep previous buy at 3)
  • firstSell = max(0, -3+5) = 2 (sell first stock for profit 2!)
  • secondBuy = max(-3, 2-5) = -3 (buying again at 5 after profit 2 nets -3)
  • secondSell = max(0, -3+5) = 2 (could sell second for profit 2)

Step 4: Day 3 (price = 0)

  • firstBuy = max(-3, -0) = 0 (buying at 0 costs nothing!)
  • firstSell = max(2, 0+0) = 2 (keep previous sell profit of 2)
  • secondBuy = max(-3, 2-0) = 2 (buy second stock at 0, using first profit of 2)
  • secondSell = max(2, 2+0) = 2 (selling at 0 doesn't help)

Step 5: Day 4 (price = 0)

  • firstBuy = max(0, 0) = 0 (same as before)
  • firstSell = max(2, 0+0) = 2 (no change)
  • secondBuy = max(2, 2-0) = 2 (no change)
  • secondSell = max(2, 2+0) = 2 (no change)

Step 6: Day 5 (price = 3)

  • firstBuy = max(0, -3) = 0 (keep buy at 0)
  • firstSell = max(2, 0+3) = 3 (new best: buy at 0, sell at 3 = 3)
  • secondBuy = max(2, 3-3) = 2 (keep second buy with net profit 2)
  • secondSell = max(2, 2+3) = 5 (second sell gives 5!)

Step 7: Day 6 (price = 1)

  • firstBuy = max(0, -1) = 0 (keep buy at 0)
  • firstSell = max(3, 0+1) = 3 (keep previous sell)
  • secondBuy = max(2, 3-1) = 2 (no improvement)
  • secondSell = max(5, 2+1) = 5 (keep previous)

Step 8: Day 7 (price = 4)

  • firstBuy = max(0, -4) = 0 (keep buy at 0)
  • firstSell = max(3, 0+4) = 4 (new best single trade: buy 0, sell 4)
  • secondBuy = max(2, 4-4) = 2 (keep second buy)
  • secondSell = max(5, 2+4) = 6 (new best combined: 6!)

Result: secondSell = 6

State Machine DP — Four States Updated Each Day — Watch how four state variables (firstBuy, firstSell, secondBuy, secondSell) update as we process each day's price, tracking the best profit achievable at each trading stage.

Algorithm

  1. Initialize four state variables:
    • firstBuy = -prices[0] (profit after buying first stock on day 0)
    • firstSell = 0 (no sell yet)
    • secondBuy = -prices[0] (hypothetical second buy on day 0)
    • secondSell = 0 (no second sell yet)
  2. For each subsequent day with price p:
    • firstBuy = max(firstBuy, -p) — buy first stock at cheaper price?
    • firstSell = max(firstSell, firstBuy + p) — sell first stock at higher price?
    • secondBuy = max(secondBuy, firstSell - p) — buy second using first trade's profit?
    • secondSell = max(secondSell, secondBuy + p) — sell second for combined profit?
  3. Return secondSell

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int firstBuy = INT_MIN, firstSell = 0;
        int secondBuy = INT_MIN, secondSell = 0;
        
        for (int price : prices) {
            firstBuy = max(firstBuy, -price);
            firstSell = max(firstSell, firstBuy + price);
            secondBuy = max(secondBuy, firstSell - price);
            secondSell = max(secondSell, secondBuy + price);
        }
        
        return secondSell;
    }
};
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        first_buy = float('-inf')
        first_sell = 0
        second_buy = float('-inf')
        second_sell = 0
        
        for price in prices:
            first_buy = max(first_buy, -price)
            first_sell = max(first_sell, first_buy + price)
            second_buy = max(second_buy, first_sell - price)
            second_sell = max(second_sell, second_buy + price)
        
        return second_sell
class Solution {
    public int maxProfit(int[] prices) {
        int firstBuy = Integer.MIN_VALUE, firstSell = 0;
        int secondBuy = Integer.MIN_VALUE, secondSell = 0;
        
        for (int price : prices) {
            firstBuy = Math.max(firstBuy, -price);
            firstSell = Math.max(firstSell, firstBuy + price);
            secondBuy = Math.max(secondBuy, firstSell - price);
            secondSell = Math.max(secondSell, secondBuy + price);
        }
        
        return secondSell;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through the prices array. At each of the n days, we perform exactly 4 constant-time max operations and 4 additions. Total work is O(4n) = O(n).

Space Complexity: O(1)

We use exactly four integer variables (firstBuy, firstSell, secondBuy, secondSell) regardless of input size. No arrays, hash maps, or other data structures are needed.