Best Time to Buy and Sell Stock III

return maximum profit with 2 transaction

Best Time to Buy and Sell Stock III

Problem

You are given an array prices. The value prices[i] is the price of a stock on day i.

Find the maximum profit you can make. You can complete at most two transactions.

One transaction means one buy and one sell. You cannot hold more than one share at a time. You must sell the stock before you buy again.

Examples

Example 1

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

• Buy on day 4 (price = 0) and sell on day 6 (price = 3). Profit = 3 - 0 = 3.
• Buy on day 7 (price = 1) and sell on day 8 (price = 4). Profit = 4 - 1 = 3.
• Total profit = 3 + 3 = 6.

Example 2

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

• Buy on day 1 (price = 1) and sell on day 5 (price = 5).
• Total profit = 5 - 1 = 4.
• We cannot buy on day 1 and buy again on day 2. We must sell first.

Example 3

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

• The price only goes down, so we make no transaction.
• The maximum profit is 0.

Constraints

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

Main Idea

This problem is like the previous one, but now we have a limit on the number of transactions. So we add one more state called cap. It tells us how many transactions are left.

Now we track three things:

• index: the current day.
• buy: 1 means we can buy. 0 means we hold a stock and can sell.
• cap: the number of transactions we can still do.

On each day, we have two choices.

When we are allowed to buy (buy = 1):

• Take: Buy today. We add -prices[index]. Then we move to the next day with buy = 0. cap stays the same.
• Not take: Do nothing. We move to the next day with buy = 1.

When we are allowed to sell (buy = 0):

• Take: Sell today. We add prices[index]. Then we move to the next day with buy = 1. Now one transaction is complete, so we do cap - 1.
• Not take: Do nothing. We move to the next day with buy = 0.

We take the maximum of both choices.

Important: We reduce cap only when we sell, because a transaction is complete only after the sell.

Base Cases

• If cap === 0, we cannot do more transactions. Return 0.
• If index === n, the days are over. Return 0.

Example: How It Works

Let us take prices = [1, 4, 2, 5] with cap = 2.

• Option 1: Buy at 1, sell at 5. Profit = 4. This uses only one transaction.
• Option 2: Buy at 1, sell at 4. Profit = 3. Then buy at 2, sell at 5. Profit = 3. Total = 6.

The code tries both options and returns the bigger one. So the answer is 6.

Solution 1: Memoization with Map (Top-Down)

We use a Map to save answers. The key is a string made from index, buy and cap.

var maxProfit = function (prices) {
    let n = prices.length;

    let map = new Map();

    function recurr(index, buy, cap) {
        // no transactions left
        if (cap === 0) {
            return 0;
        }

        // all days are over
        if (index === n) {
            return 0;
        }

        let key = `${index}#${buy}#${cap}`;

        // answer is already saved
        if (map.has(key)) {
            return map.get(key);
        }

        let profit = 0;

        if (buy) {
            // buy today OR skip today
            let take = -prices[index] + recurr(index + 1, 0, cap);
            let notTake = recurr(index + 1, 1, cap);

            profit = Math.max(take, notTake);
        } else {
            // sell today OR skip today
            let take = prices[index] + recurr(index + 1, 1, cap - 1);
            let notTake = recurr(index + 1, 0, cap);

            profit = Math.max(take, notTake);
        }

        map.set(key, profit);
        return profit;
    }

    return recurr(0, 1, 2);
};

Tip: In your code, profit was declared outside the function. It is safer to declare it with let inside the function, so each call has its own value.

Complexity

• Time Complexity: O(n * 2 * 3), which is O(n)
  • There are n * 2 * 3 different states, and each state is solved only once.
  • Building the string key adds a small cost for each state.
• Space Complexity: O(n)
  • The Map stores up to n * 2 * 3 values.
  • The recursion stack also uses O(n) extra space.

Solution 2: Memoization with 3D Array (Top-Down)

This is the same idea. But now we use a 3D array instead of a Map. It is faster, because we do not need to build string keys.

The array dp[index][buy][cap] stores the answer for each state. We fill it with -1 to show that a state is not solved yet.

var maxProfit = function (prices) {
    let n = prices.length;

    let dp = Array.from({ length: n }, () =>
        Array.from({ length: 2 }, () => Array(3).fill(-1))
    );

    function recurr(index, buy, cap) {
        // no transactions left OR all days are over
        if (cap === 0 || index === n) {
            return 0;
        }

        // answer is already saved
        if (dp[index][buy][cap] !== -1) {
            return dp[index][buy][cap];
        }

        let profit = 0;

        if (buy) {
            // buy today OR skip today
            let take = -prices[index] + recurr(index + 1, 0, cap);
            let notTake = recurr(index + 1, 1, cap);

            profit = Math.max(take, notTake);
        } else {
            // sell today OR skip today
            let take = prices[index] + recurr(index + 1, 1, cap - 1);
            let notTake = recurr(index + 1, 0, cap);

            profit = Math.max(take, notTake);
        }

        dp[index][buy][cap] = profit;
        return profit;
    }

    return recurr(0, 1, 2);
};

Complexity

• Time Complexity: O(n)
  • There are n * 2 * 3 states, and each state is solved only once.
• Space Complexity: O(n)
  • The dp table has n * 2 * 3 cells.
  • The recursion stack uses O(n) extra space.

Solution 3: Tabulation (Bottom-Up)

In this method, we do not use recursion. We start from the last day and move to the first day.

Here, dp[index][buy][cap] means: the maximum profit from day index to the end, in the state buy, with cap transactions left.

The table has n + 1 rows. The extra row dp[n] is filled with 0, and it is our base case. Also, cap = 0 stays 0 for all states, so we start the cap loop from 1.

var maxProfit = function (prices) {
    let n = prices.length;

    // all values start from 0, so base cases are already set
    let dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: 2 }, () => Array(3).fill(0))
    );

    for (let index = n - 1; index >= 0; index--) {
        for (let buy = 0; buy <= 1; buy++) {
            for (let cap = 1; cap <= 2; cap++) {
                let profit = 0;

                if (buy) {
                    // buy today OR skip today
                    let take = -prices[index] + dp[index + 1][0][cap];
                    let notTake = dp[index + 1][1][cap];

                    profit = Math.max(take, notTake);
                } else {
                    // sell today OR skip today
                    let take = prices[index] + dp[index + 1][1][cap - 1];
                    let notTake = dp[index + 1][0][cap];

                    profit = Math.max(take, notTake);
                }

                dp[index][buy][cap] = profit;
            }
        }
    }

    // start from day 0, we can buy, and we have 2 transactions
    return dp[0][1][2];
};

Complexity

• Time Complexity: O(n)
  • We use three loops. But the two inner loops run only 2 times each.
  • Each cell is filled in constant time.
• Space Complexity: O(n)
  • The dp table has (n + 1) * 2 * 3 cells.
  • There is no recursion stack.

Comparison

Summary

• This is a dynamic programming problem with three states: the day, can buy or sell, and the transactions left.
• On each day, we have two choices: do the action (buy or sell) or skip the day.
• We reduce cap only when we sell.
• A 3D array is faster than a Map, because we do not build string keys.
• All solutions run in O(n) time and use O(n) space.
• Tabulation avoids recursion, so it is safer for long arrays. This matters here, because n can be up to 10^5.