DSA

Best Time to Buy and Sell Stock - II

Covers: Recursive, Memoized, Tabulation. Optimal — Time O(2n), Space O(1).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePractice

Practice Link

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Intuition#

At any point we have two options:

  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 model the problem with two state variables: the current day index and a boolean buy flag indicating whether we currently hold a stock or are free to buy. At each day we branch: if holding nothing we can skip or buy; if holding a stock we can skip or sell. The recursion explores every possible sequence of transactions and returns the maximum profit. Because there are no cached results, the same (idx, buy) states are recomputed in multiple branches, leading to O(2^n) time.

cpp
class Solution {
public:
    int solve(vector<int> &prices, int idx, bool buy)
    {
        if(idx == prices.size())
            return 0;
        
        int profit = 0;
        if(buy)
            profit += max(solve(prices, idx+1, 1), -prices[idx] + solve(prices, idx+1, 0));
        else
            profit += max(solve(prices, idx+1, 0), prices[idx] + solve(prices, idx+1, 1));

        return profit;
    }

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

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 buy, vector<vector<int>> &memo)
    {
        if(idx == prices.size())
            return 0;
        
        int profit = 0;

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

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

        return memo[idx][buy] = profit;
    }

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

Time Complexity: O(2n)

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

Tabulation Approach#

Convert the top-down recursion into a bottom-up iteration. dp[idx][buy] holds the maximum profit achievable from day idx onward given the current buy/sell state. We fill the table from the last day backwards, so each cell depends only on the already-computed next row dp[idx+1]. This eliminates the recursive call stack entirely while keeping the same O(2n) time and O(2n) space.

cpp

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

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

Time Complexity: O(2n)

Space Complexity: O(2n)

Space Optimized#

Notice that each row dp[idx] depends only on the next row dp[idx+1]. We can therefore discard the full table and keep only two arrays (prev and curr) representing the "next day" and "current day" states respectively. After processing each day, curr is copied into prev. Space drops from O(2n) to O(1) — just two 2-element arrays — with no change to the time complexity.

cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> prev(2,0);
        vector<int> curr(2,0);

        for(int idx=n-1;idx>=0;idx--)
        {
            for(int buy=0;buy<=1;buy++)
            {
                int profit=0;
                if(buy)
                    profit += max(prev[1], -prices[idx] + prev[0]);
                else
                    profit += max(prev[0], prices[idx] + prev[1]);
                curr[buy] = profit;
            }
            prev = curr;
        }
        return prev[1];
    }
};

Time Complexity: O(2n)

Space Complexity: O(1)

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