Problem Description

The Best Time to Buy and Sell Stock III problem asks you to maximize your profit by making at most two transactions in the stock market. You are given an array prices where prices[i] represents the price of a stock on the ith day.

• You may complete at most two transactions (a buy followed by a sell counts as one transaction).
• You cannot engage in multiple transactions at the same time (i.e., you must sell before you buy again).
• Return the maximum profit you can achieve from these transactions. If you cannot make any profit, return 0.

Constraints:

• 1 ≤ prices.length ≤ 105
• 0 ≤ prices[i] ≤ 105

Thought Process

At first glance, you might consider trying all possible pairs of buy and sell days for up to two transactions. For each possible first transaction, you could check every possible second transaction after it. However, this brute-force approach would be extremely slow for large inputs.

To optimize, we should look for patterns and ways to break the problem into manageable subproblems. We know from the single-transaction version (Best Time to Buy and Sell Stock I) that we can track the minimum price and calculate the max profit in one pass. For two transactions, we need to find two non-overlapping buy-sell pairs that together yield the highest profit.

The challenge is to efficiently find the best way to split the days into two parts, maximizing the sum of the best single-transaction profits in each part. This suggests a dynamic programming or state-tracking approach.

Solution Approach

We'll use a dynamic programming approach based on tracking profits at each day for up to two transactions. Here's how:

1. State variables:
   • first_buy: The lowest price to buy the first stock (minimize cost).
   • first_profit: The max profit after selling the first stock.
   • second_buy: The lowest effective price to buy the second stock (considering profit from the first sell).
   • second_profit: The max profit after selling the second stock (final answer).
2. Algorithm Steps:
   • Initialize first_buy and second_buy to infinity, first_profit and second_profit to zero.
   • Loop through each price:
     • Update first_buy to be the minimum of itself and the current price.
     • Update first_profit to be the maximum of itself and current price minus first_buy.
     • Update second_buy to be the minimum of itself and current price minus first_profit (effectively reinvesting the first profit).
     • Update second_profit to be the maximum of itself and current price minus second_buy.
   • At the end, second_profit is the answer.
3. Why this works:
   • We track the best profit after each transaction, updating our "effective cost" for the second buy to account for profit already made.
   • This allows us to find the optimal split between the two transactions in a single pass through the array.

This approach is both time and space efficient, requiring only constant extra space and a single loop.

Example Walkthrough

Let's use the input prices = [3,3,5,0,0,3,1,4].

• Initialize: first_buy = inf, first_profit = 0, second_buy = inf, second_profit = 0
• Day 0, price=3:
  • first_buy = min(inf, 3) = 3
  • first_profit = max(0, 3-3) = 0
  • second_buy = min(inf, 3-0) = 3
  • second_profit = max(0, 3-3) = 0
• Day 1, price=3: (no change)
• Day 2, price=5:
  • first_profit = max(0, 5-3) = 2
  • second_buy = min(3, 5-2) = 3
  • second_profit = max(0, 5-3) = 2
• Day 3, price=0:
  • first_buy = min(3, 0) = 0
  • first_profit = max(2, 0-0) = 2
  • second_buy = min(3, 0-2) = -2
  • second_profit = max(2, 0-(-2)) = 2
• Day 4, price=0: (no change)
• Day 5, price=3:
  • first_profit = max(2, 3-0) = 3
  • second_buy = min(-2, 3-3) = -2
  • second_profit = max(2, 3-(-2)) = 5
• Day 6, price=1:
  • second_buy = min(-2, 1-3) = -2
  • second_profit = max(5, 1-(-2)) = 5
• Day 7, price=4:
  • second_profit = max(5, 4-(-2)) = 6
• Final answer: 6

The two transactions are:

• Buy at 0, sell at 3 (profit=3)
• Buy at 1, sell at 4 (profit=3)

Code Implementation

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0
        first_buy = float('inf')
        first_profit = 0
        second_buy = float('inf')
        second_profit = 0
        for price in prices:
            first_buy = min(first_buy, price)
            first_profit = max(first_profit, price - first_buy)
            second_buy = min(second_buy, price - first_profit)
            second_profit = max(second_profit, price - second_buy)
        return second_profit
      

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int first_buy = INT_MAX, first_profit = 0;
        int second_buy = INT_MAX, second_profit = 0;
        for (int price : prices) {
            first_buy = min(first_buy, price);
            first_profit = max(first_profit, price - first_buy);
            second_buy = min(second_buy, price - first_profit);
            second_profit = max(second_profit, price - second_buy);
        }
        return second_profit;
    }
};
      

class Solution {
    public int maxProfit(int[] prices) {
        int firstBuy = Integer.MAX_VALUE, firstProfit = 0;
        int secondBuy = Integer.MAX_VALUE, secondProfit = 0;
        for (int price : prices) {
            firstBuy = Math.min(firstBuy, price);
            firstProfit = Math.max(firstProfit, price - firstBuy);
            secondBuy = Math.min(secondBuy, price - firstProfit);
            secondProfit = Math.max(secondProfit, price - secondBuy);
        }
        return secondProfit;
    }
}
      

var maxProfit = function(prices) {
    let firstBuy = Infinity, firstProfit = 0;
    let secondBuy = Infinity, secondProfit = 0;
    for (let price of prices) {
        firstBuy = Math.min(firstBuy, price);
        firstProfit = Math.max(firstProfit, price - firstBuy);
        secondBuy = Math.min(secondBuy, price - firstProfit);
        secondProfit = Math.max(secondProfit, price - secondBuy);
    }
    return secondProfit;
};
      

Time and Space Complexity

• Brute-force approach:
  • Would involve checking all possible pairs of transactions, leading to O(n^2) or worse, which is too slow for large inputs.
• Optimized approach (as above):
  • Time Complexity: O(n) — We only loop through the prices array once.
  • Space Complexity: O(1) — Only a constant number of variables are used, regardless of input size.

This makes the solution highly efficient and suitable for very large arrays.

Summary

The key to solving the Best Time to Buy and Sell Stock III problem is realizing that you can track the best profit for two transactions with just four variables. By carefully updating these variables as you scan through the prices, you efficiently simulate buying and selling twice for maximum gain. This approach is both elegant and fast, leveraging the insights from the single-transaction problem and extending them to handle two transactions seamlessly.