DSA

Best Time to Buy and Sell Stock with Cooldown - V

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

August 8, 2026
DSADynamic ProgrammingDPLeetCodePractice

Practice Link

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

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

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 cooldown time:

  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#

The only difference from Stock II is the cooldown: after a sell on day idx, the next allowed buy is on day idx+2 (skipping one day). We encode this by jumping to idx+2 instead of idx+1 when transitioning from the "sell" branch back to the "can buy" state. Everything else — the two-state recursion over (idx, buy) — remains identical, and the same exponential recomputation problem applies.

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+2, 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+2, 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#

We allocate a table of size (n+2) × 2 — the extra row at n+1 handles the sell-path jump to idx+2 safely without bounds checks. Iterating from day n-1 down to 0, each cell reads from dp[idx+1] (skip) or dp[idx+2] (sell with cooldown). This bottom-up fill eliminates the recursive stack and computes the answer at dp[0][1].

cpp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n+2, 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+2][1]);
                dp[idx][buy] = profit;
            }
            
        }
        return dp[0][1];
    }
};

Time Complexity: O(2n)

Space Complexity: O(2n)

Space Optimized#

The sell branch reads from dp[idx+2], so we must keep track of two "future" rows rather than one. We maintain three 2-element arrays — curr, next (idx+1), and nextToNext (idx+2). After each day we shift: nextToNext = next, next = curr. Space drops to O(1) — three constant-size arrays — while time stays O(2n).

cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> next(2,0);
        vector<int> nextToNext(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(next[1], -prices[idx] + next[0]);
                else
                    profit += max(next[0], prices[idx] + nextToNext[1]);
                curr[buy] = profit;
            }
            nextToNext = next;
            next = curr;
        }
        return next[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>).