309. Best Time to Buy Sell Stock Cooldown

The problem

You are given an array prices where prices[i] is the price of a given stock on the i^th 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).

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

Approach overview

Problem Overview: You are given an array prices where prices[i] is the stock price on day i. You can buy and sell multiple times, but after selling a stock you must wait one day before buying again (cooldown). The goal is to compute the maximum profit achievable under this constraint.

Approach 1: Recursive DP with Memoization (Time: O(n), Space: O(n))

Model the decision process day by day. At each index you track whether you are allowed to buy or you currently hold a stock. From a buy state, you either buy the stock and move to the sell state or skip the day. From a sell state, you either sell the stock and jump two days forward (due to the cooldown) or skip the day. A naive recursion explores many repeated states, so memoization stores results for each pair (day, holdingState). This converts the exponential search into linear time because each state is solved once. This approach clearly expresses the decision tree and is useful when first reasoning about the dynamic programming state transitions.

Approach 2: Iterative Dynamic Programming (State Machine) (Time: O(n), Space: O(1))

The optimal solution tracks three states while scanning the array once. hold represents the best profit while holding a stock, sold represents profit immediately after selling, and rest represents profit while in cooldown or doing nothing. For each price you update the states using transitions: buying moves from rest → hold, selling moves from hold → sold, and waiting moves from sold → rest. Because each state depends only on the previous day, you keep three variables instead of an entire DP table. The algorithm performs a single pass over the prices array, updating profits in constant time per element.

The key insight is separating "holding", "just sold", and "resting" states. The cooldown restriction is naturally enforced because buying is only allowed from the rest state, not from sold. This transforms the problem into a small deterministic state machine, a common pattern in dynamic programming problems involving stock trading constraints.

Recommended for interviews: The iterative dynamic programming state-machine approach. Interviewers expect an O(n) solution with constant space and clear state transitions. Starting with the recursive memoized version demonstrates understanding of the decision process, but converting it into the compact three-state DP shows strong optimization and problem modeling skills.

Approach 1: Dynamic Programming Approach

This approach uses dynamic programming to track three states on each day: holding, not holding with cooldown, and not holding without cooldown. The idea is to decide the best action for any day based on the previous day's states. At each step, calculate the maximum profit for holding a stock, selling it, or being idle.

Python

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0
        hold, sell, cooldown = -prices[0], 0, 0
        for price in prices[1:]:
            prev_sell = sell
            sell = hold + price
            hold = max(hold, cooldown - price)
            cooldown = max(cooldown, prev_sell)
        return max(sell, cooldown)

if __name__ == '__main__':
    sol = Solution()
    prices = [1, 2, 3, 0, 2]
    print("Max Profit:", sol.maxProfit(prices))

Java

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int hold = -prices[0], sell = 0, cooldown = 0;
        for (int i = 1; i < prices.length; i++) {
            int prev_sell = sell;
            sell = hold + prices[i];
            hold = Math.max(hold, cooldown - prices[i]);
            cooldown = Math.max(cooldown, prev_sell);
        }
        return Math.max(sell, cooldown);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices = {1, 2, 3, 0, 2};
        System.out.println("Max Profit: " + sol.maxProfit(prices));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        if (prices.empty()) return 0;
        int hold = -prices[0], sell = 0, cooldown = 0;
        for (size_t i = 1; i < prices.size(); ++i) {
            int prev_sell = sell;
            sell = hold + prices[i];
            hold = std::max(hold, cooldown - prices[i]);
            cooldown = std::max(cooldown, prev_sell);
        }
        return std::max(sell, cooldown);
    }
};

int main() {
    Solution sol;
    std::vector<int> prices = {1, 2, 3, 0, 2};
    std::cout << "Max Profit: " << sol.maxProfit(prices) << std::endl;
    return 0;
}

JavaScript

function maxProfit(prices) {
    if (prices.length === 0) return 0;
    let hold = -prices[0], sell = 0, cooldown = 0;
    for (let i = 1; i < prices.length; i++) {
        let prev_sell = sell;
        sell = hold + prices[i];
        hold = Math.max(hold, cooldown - prices[i]);
        cooldown = Math.max(cooldown, prev_sell);
    }
    return Math.max(sell, cooldown);
}

console.log("Max Profit:", maxProfit([1, 2, 3, 0, 2]));

#include <stdio.h>

int maxProfit(int* prices, int pricesSize){
    if (pricesSize == 0) return 0;
    int hold = -prices[0], sell = 0, cooldown = 0;
    for (int i = 1; i < pricesSize; i++) {
        int prev_sell = sell;
        sell = hold + prices[i];
        hold = fmax(hold, cooldown - prices[i]);
        cooldown = fmax(cooldown, prev_sell);
    }
    return fmax(sell, cooldown);
}

int main() {
    int prices[] = {1,2,3,0,2};
    int size = sizeof(prices)/sizeof(prices[0]);
    printf("Max Profit: %d\n", maxProfit(prices, size));
    return 0;
}

using System;

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) return 0;
        int hold = -prices[0], sell = 0, cooldown = 0;
        for (int i = 1; i < prices.Length; i++) {
            int prev_sell = sell;
            sell = hold + prices[i];
            hold = Math.Max(hold, cooldown - prices[i]);
            cooldown = Math.Max(cooldown, prev_sell);
        }
        return Math.Max(sell, cooldown);
    }
    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] prices = {1, 2, 3, 0, 2};
        Console.WriteLine("Max Profit: " + sol.MaxProfit(prices));
    }
}

This Python solution similarly uses dynamic programming to track three states. hold, sell, and cooldown are adjusted as we realize maximum profit. max function is used to determine the most profitable action each day.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Recursive Approach with Memoization

This approach involves a recursive solution that tracks the profit by exploring all possible transactions. To optimize the solution, memoization is used to store and reuse results of repeated states to avoid redundant calculations.

Python

class Solution:
    def __init__(self):
        self.memo = {}

    def solve(self, prices, i, canBuy):
        if i >= len(prices):
            return 0
        if (i, canBuy) in self.memo:
            return self.memo[(i, canBuy)]
        cooldown = self.solve(prices, i + 1, canBuy)
        if canBuy:
            buy = self.solve(prices, i + 1, 0) - prices[i]
            self.memo[(i, canBuy)] = max(buy, cooldown)
        else:
            sell = self.solve(prices, i + 2, 1) + prices[i]
            self.memo[(i, canBuy)] = max(sell, cooldown)
        return self.memo[(i, canBuy)]

    def maxProfit(self, prices):
        return self.solve(prices, 0, 1)

if __name__ == '__main__':
    sol = Solution()
    prices = [1, 2, 3, 0, 2]
    print("Max Profit:", sol.maxProfit(prices))

Java

import java.util.Arrays;

public class Solution {
    private int[][] memo;
    
    public int solve(int[] prices, int i, int canBuy) {
        if (i >= prices.length) return 0;
        if (memo[i][canBuy] != -1) return memo[i][canBuy];
        int cooldown = solve(prices, i+1, canBuy);
        if (canBuy == 1) {
            int buy = solve(prices, i+1, 0) - prices[i];
            memo[i][canBuy] = Math.max(buy, cooldown);
        } else {
            int sell = solve(prices, i+2, 1) + prices[i];
            memo[i][canBuy] = Math.max(sell, cooldown);
        }
        return memo[i][canBuy];
    }

    public int maxProfit(int[] prices) {
        memo = new int[prices.length][2];
        for (int[] row : memo) Arrays.fill(row, -1);
        return solve(prices, 0, 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices = {1, 2, 3, 0, 2};
        System.out.println("Max Profit: " + sol.maxProfit(prices));
    }
}

C++

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int memo[5000][2];

int solve(vector<int>& prices, int i, int canBuy) {
    if (i >= prices.size()) return 0;
    if (memo[i][canBuy] != -1) return memo[i][canBuy];
    int cooldown = solve(prices, i + 1, canBuy);
    if (canBuy) {
        int buy = solve(prices, i + 1, 0) - prices[i];
        memo[i][canBuy] = max(buy, cooldown);
    } else {
        int sell = solve(prices, i + 2, 1) + prices[i];
        memo[i][canBuy] = max(sell, cooldown);
    }
    return memo[i][canBuy];
}

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

int main() {
    vector<int> prices = {1, 2, 3, 0, 2};
    cout << "Max Profit: " << maxProfit(prices) << endl;
    return 0;
}

JavaScript

let memo = {};

function solve(prices, i, canBuy) {
    if (i >= prices.length) return 0;
    let key = `${i}-${canBuy}`;
    if (key in memo) return memo[key];
    let cooldown = solve(prices, i + 1, canBuy);
    if (canBuy === 1) {
        let buy = solve(prices, i + 1, 0) - prices[i];
        memo[key] = Math.max(buy, cooldown);
    } else {
        let sell = solve(prices, i + 2, 1) + prices[i];
        memo[key] = Math.max(sell, cooldown);
    }
    return memo[key];
}

function maxProfit(prices) {
    memo = {};
    return solve(prices, 0, 1);
}

console.log("Max Profit:", maxProfit([1, 2, 3, 0, 2]));

#include <stdio.h>
#include <string.h>

int memo[5000][2];

int solve(int* prices, int n, int i, int canBuy) {
    if (i >= n) return 0;
    if (memo[i][canBuy] != -1) return memo[i][canBuy];
    int cooldown = solve(prices, n, i + 1, canBuy);
    if (canBuy) {
        int buy = solve(prices, n, i + 1, 0) - prices[i];
        memo[i][canBuy] = (buy > cooldown) ? buy : cooldown;
    } else {
        int sell = solve(prices, n, i + 2, 1) + prices[i];
        memo[i][canBuy] = (sell > cooldown) ? sell : cooldown;
    }
    return memo[i][canBuy];
}

int maxProfit(int* prices, int pricesSize) {
    memset(memo, -1, sizeof(memo));
    return solve(prices, pricesSize, 0, 1);
}

int main() {
    int prices[] = {1, 2, 3, 0, 2};
    int size = sizeof(prices) / sizeof(prices[0]);
    printf("Max Profit: %d\n", maxProfit(prices, size));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<Tuple<int, int>, int> memo = new Dictionary<Tuple<int, int>, int>();

    public int Solve(int[] prices, int i, int canBuy) {
        if (i >= prices.Length) return 0;
        var key = Tuple.Create(i, canBuy);
        if (memo.ContainsKey(key)) return memo[key];
        int cooldown = Solve(prices, i + 1, canBuy);
        if (canBuy == 1) {
            int buy = Solve(prices, i + 1, 0) - prices[i];
            memo[key] = Math.Max(buy, cooldown);
        } else {
            int sell = Solve(prices, i + 2, 1) + prices[i];
            memo[key] = Math.Max(sell, cooldown);
        }
        return memo[key];
    }

    public int MaxProfit(int[] prices) {
        return Solve(prices, 0, 1);
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] prices = {1, 2, 3, 0, 2};
        Console.WriteLine("Max Profit: " + sol.MaxProfit(prices));
    }
}

This Python implementation uses a dictionary for memoization and a recursive function solve that handles state transitions and profit calculations, thus efficiently determining maximum profit through stored results of previously computed states.

Complexity

Time Complexity: O(n).
Space Complexity: O(n).

Try this approach in the editor

Approach 3: Memoization Search

We design a function dfs(i, j), which represents the maximum profit that can be obtained starting from the ith day with state j. The values of j are 0 and 1, respectively representing currently not holding a stock and holding a stock. The answer is dfs(0, 0).

The execution logic of the function dfs(i, j) is as follows:

If i geq n, it means that there are no more stocks to trade, so return 0;

Otherwise, we can choose not to trade, then dfs(i, j) = dfs(i + 1, j). We can also trade stocks. If j > 0, it means that we currently hold a stock and can sell it, then dfs(i, j) = prices[i] + dfs(i + 2, 0). If j = 0, it means that we currently do not hold a stock and can buy, then dfs(i, j) = -prices[i] + dfs(i + 1, 1). Take the maximum value as the return value of the function dfs(i, j).

The answer is dfs(0, 0).

To avoid repeated calculations, we use the method of memoization search, and use an array f to record the return value of dfs(i, j). If f[i][j] is not -1, it means that it has been calculated, and we can directly return f[i][j].

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array prices.

TypeScript

function maxProfit(prices: number[]): number {
    const n = prices.length;
    const f: number[][] = Array.from({ length: n }, () => Array.from({ length: 2 }, () => -1));
    const dfs = (i: number, j: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        let ans = dfs(i + 1, j);
        if (j) {
            ans = Math.max(ans, prices[i] + dfs(i + 2, 0));
        } else {
            ans = Math.max(ans, -prices[i] + dfs(i + 1, 1));
        }
        return (f[i][j] = ans);
    };
    return dfs(0, 0);
}

func maxProfit(prices []int) int {
	n := len(prices)
	f := make([][2]int, n)
	for i := range f {
		f[i] = [2]int{-1, -1}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= n {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := dfs(i+1, j)
		if j > 0 {
			ans = max(ans, prices[i]+dfs(i+2, 0))
		} else {
			ans = max(ans, -prices[i]+dfs(i+1, 1))
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, 0)
}

Try this approach in the editor

Approach 4: Dynamic Programming

We can also use dynamic programming to solve this problem.

We define f[i][j] to represent the maximum profit that can be obtained on the ith day with state j. The values of j are 0 and 1, respectively representing currently not holding a stock and holding a stock. Initially, f[0][0] = 0, f[0][1] = -prices[0].

When i geq 1, if we currently do not hold a stock, then f[i][0] can be obtained by transitioning from f[i - 1][0] and f[i - 1][1] + prices[i], i.e., f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]). If we currently hold a stock, then f[i][1] can be obtained by transitioning from f[i - 1][1] and f[i - 2][0] - prices[i], i.e., f[i][1] = max(f[i - 1][1], f[i - 2][0] - prices[i]). The final answer is f[n - 1][0].

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array prices.

We notice that the transition of state f[i][] is only related to f[i - 1][] and f[i - 2][0], so we can use three variables f, f_0, f_1 to replace the array f, optimizing the space complexity to O(1).

TypeScript

function maxProfit(prices: number[]): number {
    const n = prices.length;
    const f: number[][] = Array.from({ length: n }, () => Array.from({ length: 2 }, () => 0));
    f[0][1] = -prices[0];
    for (let i = 1; i < n; ++i) {
        f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
        f[i][1] = Math.max(f[i - 1][1], (i > 1 ? f[i - 2][0] : 0) - prices[i]);
    }
    return f[n - 1][0];
}

func maxProfit(prices []int) int {
	n := len(prices)
	f := make([][2]int, n)
	f[0][1] = -prices[0]
	for i := 1; i < n; i++ {
		f[i][0] = max(f[i-1][0], f[i-1][1]+prices[i])
		if i > 1 {
			f[i][1] = max(f[i-1][1], f[i-2][0]-prices[i])
		} else {
			f[i][1] = max(f[i-1][1], -prices[i])
		}
	}
	return f[n-1][0]
}

Try this approach in the editor

Approach 5: Default Approach

TypeScript

function maxProfit(prices: number[]): number {
    let [f, f0, f1] = [0, 0, -prices[0]];
    for (const x of prices.slice(1)) {
        [f, f0, f1] = [f0, Math.max(f0, f1 + x), Math.max(f1, f - x)];
    }
    return f0;
}

func maxProfit(prices []int) int {
	f, f0, f1 := 0, 0, -prices[0]
	for _, x := range prices[1:] {
		f, f0, f1 = f0, max(f0, f1+x), max(f1, f-x)
	}
	return f0
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n). Space Complexity: O(1).
Recursive Approach with Memoization	Time Complexity: O(n). Space Complexity: O(n).
Memoization Search	–
Dynamic Programming	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive DP with Memoization	O(n)	O(n)	When reasoning about decisions (buy, sell, skip) and building intuition for the DP states
Iterative Dynamic Programming (State Machine)	O(n)	O(1)	Optimal solution for interviews and production due to constant space and single pass

Frequently asked questions

Is Best Time to Buy and Sell Stock with Cooldown easy or hard?

The problem is rated Medium because the difficulty comes from modeling the cooldown constraint correctly. Once the three-state dynamic programming relationship is identified, the implementation becomes a straightforward linear scan.

Best Time to Buy and Sell Stock with Cooldown Python/Java solution

Python and Java implementations typically follow the same DP state-machine logic. Maintain three variables (hold, sold, rest) and update them for each price in the array. The algorithm runs in O(n) time and O(1) space regardless of the programming language.

How to solve Best Time to Buy and Sell Stock with Cooldown in O(n)?

Track three DP states while iterating through the prices: hold (profit while holding a stock), sold (profit after selling today), and rest (profit while not holding and not selling). Update them using transitions hold = max(hold, rest - price), sold = hold + price, and rest = max(rest, previousSold). This single pass guarantees O(n) time.

What is the best approach for Best Time to Buy and Sell Stock with Cooldown?

The most efficient approach is iterative Dynamic Programming using three states: hold, sold, and rest. Each state represents the maximum profit while holding a stock, after selling, or resting due to cooldown. The algorithm updates these states in a single pass through the prices array, achieving O(n) time and O(1) space.

Is Best Time to Buy and Sell Stock with Cooldown asked at Google/Amazon/Meta?

Stock trading dynamic programming problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as transaction fees, cooldown periods, or limited transactions test a candidate's ability to design DP state transitions.

What data structure is used in Best Time to Buy and Sell Stock with Cooldown?

The solution primarily uses dynamic programming variables rather than complex data structures. The input is an array of prices, and the optimal algorithm maintains a few variables representing DP states such as hold, sold, and rest while iterating through the array.

What is the time complexity of Best Time to Buy and Sell Stock with Cooldown?

The optimal dynamic programming solution runs in O(n) time where n is the number of days in the prices array. Each price is processed once while updating a constant number of DP states. Space complexity can be reduced to O(1) by storing only the previous state values.

Best Time to Buy and Sell Stock with Cooldown solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Recursive Approach with Memoization

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Best Time to Buy and Sell Stock with Cooldown solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Recursive Approach with Memoization

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems