DSA

Best Time to Buy and Sell Stock - III

Covers: Recursive, Memoized. Optimal — Time O(n), Space O(2 * 3).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePractice

Practice Link

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).

Intiution#

At any point we have two options just keep check for the maximum possible transactions:

  1. Buy a stock (only if previously not bought)
  • Do not sell - no transaction
  • sell stock
  1. Sell a stock (only if previously bought)
  • Do not buy - no transaction
  • buy stock

Recursive Approach#

We extend the Stock II state space with a third dimension: the number of remaining transactions. The state (idx, canBuy, transactions) captures where we are, whether we can buy, and how many complete buy-sell rounds are still allowed. On every sell we decrement the transaction counter; when it hits zero or we exhaust all days, we return 0. The same state can be reached through many paths, causing exponential recomputation.

cpp
class Solution {
public:

    int solve(vector<int> &prices, int idx, bool canBuy, int transactions)
    {
        if(transactions==0 || idx == prices.size())
            return 0;

        int profit = 0;

        if(canBuy)
            profit += max(solve(prices, idx+1, 1, transactions), -prices[idx] + solve(prices, idx+1, 0, transactions));
        else
            profit += max(solve(prices, idx+1, 0, transactions), prices[idx] + solve(prices, idx+1, 1, transactions-1));

        return profit;
    }

    int maxProfit(vector<int>& prices) {
        return solve(prices, 0,1, 2);
    }
};

Time Complexity: O(2^n) --> TLE

Space Complexity: O(n)

Memoized Approach#

Memoization stores already computed results in a dp array to avoid recalculations. This optimizes the recursive approach, reducing redundant computations while still exploring all possible outcomes.

cpp
class Solution {
public:
    int solve(vector<int> &prices, int idx, bool canBuy, int transactions, vector<vector<vector<int>>> &memo)
    {
        if(transactions==0 || idx == prices.size())
            return 0;
        
        int profit = 0;

        if(memo[idx][canBuy][transactions] != -1)
            return memo[idx][canBuy][transactions];

        if(canBuy)
            profit += max(solve(prices, idx+1, 1,transactions, memo), -prices[idx] + solve(prices, idx+1, 0,transactions, memo));
        else
            profit += max(solve(prices, idx+1, 0,transactions, memo), prices[idx] + solve(prices, idx+1, 1,transactions-1, memo));

        return memo[idx][canBuy][transactions] = profit;
    }

    int maxProfit(vector<int>& prices) {
        int transactions = 2;
        vector<vector<vector<int>>> memo(prices.size(), vector<vector<int>> (2, vector<int>(transactions+1, -1)));
        return solve(prices, 0, 1,transactions, memo);
    }
};

Time Complexity: O(2 * 3 n) ~ O(n)

Space Complexity: O(2 * 3 * n) + O(n) (Recursive stack)

Tabulation#

Build the solution bottom-up with a 3D table dp[idx][buy][t] where t is the remaining transaction count. We fill the table from the last day back to day 0, ensuring that dp[idx+1] is always available when we compute dp[idx]. Each of the n × 2 × 3 cells is filled in O(1), giving O(n) overall time. The recursion stack overhead is eliminated compared to memoization.

cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int transactions = 2;
        vector<vector<vector<int>>> dp(prices.size()+1, vector<vector<int>> (2, vector<int>(transactions+1, 0)));

        for(int idx=prices.size()-1;idx>=0;idx--)
        {
            for(int buy=0;buy<=1;buy++)
            {
                for(int t=1;t<=2;t++)
                {
                    int profit=0;
                    if(buy)
                        profit = max(dp[idx+1][1][t], -prices[idx] + dp[idx+1][0][t]);
                    else
                        profit = max(dp[idx+1][0][t], prices[idx] + dp[idx+1][1][t-1]);
                    dp[idx][buy][t] = profit;
                }   
            }
        }

        return dp[0][1][2];
    }
};

Time Complexity: O(2 * 3 n) ~ O(n)

Space Complexity: O(2 * 3 * n)

Space Optimized Tabulation#

Since each row dp[idx] only reads from dp[idx+1], we can replace the full 3D table with two 2D arrays (next and curr) of size 2 × (transactions+1). After each day we swap curr into next. Space shrinks from O(2 × 3 × n) to O(2 × 3) — a constant — with identical time complexity.

cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int transactions = 2;

        vector<vector<int>> next(2, vector<int>(transactions+1, 0));
        vector<vector<int>> curr(2, vector<int>(transactions+1, 0));

        for(int idx=prices.size()-1;idx>=0;idx--)
        {
            for(int buy=0;buy<=1;buy++)
            {
                for(int t=1;t<=2;t++)
                {
                    int profit=0;
                    if(buy)
                        profit = max(next[1][t], -prices[idx] + next[0][t]);
                    else
                        profit = max(next[0][t], prices[idx] + next[1][t-1]);
                    curr[buy][t] = profit;
                }   
            }
            next = curr;
        }

        return next[1][2];
    }
};

Time Complexity: O(2 * 3 n) ~ O(n)

Space Complexity: O(2 * 3)

Related articles

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).