Log inSign up
mediumLeetCodeNot Started

Best Time to Buy and Sell Stock with Cooldown

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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., 1 day cooldown). - 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] - Buy on day 1 (price = 1), sell on day 2 (price = 2) -> profit = 1 - Cooldown on day 3 - Buy on day 4 (price = 0), sell on day 5 (price = 2) -> profit = 2 - Total profit = 1 + 2 = 3.

### Example 2 - Input: prices = [1] - Output: 0 - Explanation: No transactions possible.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Design Finite State Machine (FSM) representations for constrained DP problems.
  • Prevent illegal state transitions (buying on cooldown) by separating Sold and Rest states.
  • Reduce 3 arrays to 3 scalar variables.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Stock trading problem with cooldown constraint after selling.
  • State transitions depend on what happened 1 or 2 days prior.

Algorithmic Decision Tree:

  • Create explicit states: Hold, Sold, Rest.
  • Buying is only permitted from the Rest state, never immediately from Sold.

Connected Patterns:

Best Time to Buy and Sell Stock IIPaint House (state transitions)

1. Recursive Decision Tree with Cooldown Flag

Intuition

Recursively explore states solve(day, state) where state can be 0 (ready to buy), 1 (holding stock), or 2 (cooldown day).

Algorithm

  1. Define dfs(day, state).
  2. If day == n, return 0.
  3. If state == 1 (holding): choice 1 is sell prices[day] + dfs(day + 1, 2); choice 2 is keep dfs(day + 1, 1).
  4. If state == 2 (cooldown): must transition to rest dfs(day + 1, 0).
  5. If state == 0 (rest): choice 1 is buy -prices[day] + dfs(day + 1, 1); choice 2 is skip dfs(day + 1, 0).
  6. Return max of choices.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int day, int state, const vector<int>& prices) {
8 if (day == (int)prices.size()) return 0;
9 if (state == 1) { // holding
10 int sell = prices[day] + dfs(day + 1, 2, prices);
11 int keep = dfs(day + 1, 1, prices);
12 return max(sell, keep);
13 } else if (state == 2) { // cooldown
14 return dfs(day + 1, 0, prices);
15 } else { // rest / can buy
16 int buy = -prices[day] + dfs(day + 1, 1, prices);
17 int skip = dfs(day + 1, 0, prices);
18 return max(buy, skip);
19 }
20}
21
22int maxProfitRecursive(const vector<int>& prices) {
23 return dfs(0, 0, prices);
24}
25
26int main() {
27 vector<int> prices = {1, 2, 3, 0, 2};
28 cout << "Max Profit (Recursive): " << maxProfitRecursive(prices) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. 3-Array Tabulation Dynamic Programming

Intuition

Construct three DP arrays hold[n], sold[n], and rest[n] where each entry tracks the maximum profit ending that day in that state.

Algorithm

  1. hold[0] = -prices[0], sold[0] = 0, rest[0] = 0.
  2. For i = 1 to n - 1:
  3. hold[i] = max(hold[i - 1], rest[i - 1] - prices[i])
  4. sold[i] = hold[i - 1] + prices[i]
  5. rest[i] = max(rest[i - 1], sold[i - 1])
  6. Return max(sold[n - 1], rest[n - 1]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfit3Arrays(const vector<int>& prices) {
8 int n = prices.size();
9 if (n <= 1) return 0;
10
11 vector<int> hold(n, 0), sold(n, 0), rest(n, 0);
12 hold[0] = -prices[0];
13 sold[0] = 0;
14 rest[0] = 0;
15
16 for (int i = 1; i < n; i++) {
17 hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]);
18 sold[i] = hold[i - 1] + prices[i];
19 rest[i] = max(rest[i - 1], sold[i - 1]);
20 }
21 return max(sold[n - 1], rest[n - 1]);
22}
23
24int main() {
25 vector<int> prices = {1, 2, 3, 0, 2};
26 cout << "Max Profit (3-Array DP): " << maxProfit3Arrays(prices) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for 3 DP arrays

3. Constant Space O(1) State Machine DP

Intuition

Maintain three scalar variables hold, sold, and rest updated in a single forward pass.

Algorithm

  1. hold = -prices[0], sold = 0, rest = 0.
  2. For each price in prices (or from index 1):
  3. prevSold = sold
  4. sold = hold + price
  5. hold = max(hold, rest - price)
  6. rest = max(rest, prevSold)
  7. Return max(sold, rest).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitOptimal(const vector<int>& prices) {
8 if (prices.empty()) return 0;
9 int hold = -prices[0];
10 int sold = 0;
11 int rest = 0;
12
13 for (size_t i = 1; i < prices.size(); i++) {
14 int prevSold = sold;
15 sold = hold + prices[i];
16 hold = max(hold, rest - prices[i]);
17 rest = max(rest, prevSold);
18 }
19 return max(sold, rest);
20}
21
22int main() {
23 vector<int> prices = {1, 2, 3, 0, 2};
24 cout << "Max Profit (Optimal O(1) Space): " << maxProfitOptimal(prices) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive TreeO(2^n)O(n)Recursion exploring buy, sell, cooldown.Redundant states
2.3-Array DPO(n)O(n)hold, sold, rest arrays.Array memory
3.State Machine ScalarsOptimalO(n)O(1)hold, sold, rest updated with prevSold temp variable.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Updating rest with the newly computed sold of today instead of prevSold (yesterday's sold): This violates the 1-day cooldown period.

Pitfall 2:

Forgetting to check max(sold, rest) at the end (the optimal state could end on an idle rest day).

Crucial Edge Cases to Validate:

  • Prices length <= 1: Profit is 0.
  • Prices strictly decreasing: Profit is 0.
  • Two days: Buy day 0, sell day 1 if prices[1] > prices[0].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the 3-state transition graph on the whiteboard. Explain each arrow clearly: Hold -> Sold (sell), Sold -> Rest (mandatory cooldown), Rest -> Hold (buy), Rest -> Rest (skip).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can the hold state only transition from rest - price and NOT from sold - price?

Back to DSA Sheet