Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock with Cooldown - 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).
You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Input & Output

Example 1 — Basic Transaction Pattern

$ Input: prices = [1,2,3,0,2]

› Output: 3

💡 Note: Buy on day 0 (price=1), sell on day 2 (price=3), cooldown on day 3, buy on day 3 (price=0), sell on day 4 (price=2). Total profit = (3-1) + (2-0) = 4. Wait, that's wrong. Actually: buy day 0 (price=1), sell day 2 (price=3) for profit 2, cooldown day 3, buy day 3 (price=0) is impossible since we're in cooldown. Correct: buy day 0, sell day 2, profit=2. Or buy day 3, sell day 4, profit=2. Or buy day 0, sell day 1, profit=1, cooldown day 2, buy day 3, sell day 4, profit=2, total=3.

Example 2 — All Increasing Prices

$ Input: prices = [2,4,1]

› Output: 2

💡 Note: Buy on day 0 (price=2), sell on day 1 (price=4). Profit = 4-2 = 2. Cannot buy on day 2 due to cooldown, and price is lower anyway.

Example 3 — Single Transaction Only

$ Input: prices = [1,2]

› Output: 1

💡 Note: Buy on day 0 (price=1), sell on day 1 (price=2). Profit = 2-1 = 1.

Constraints

1 ≤ prices.length ≤ 5000
0 ≤ prices[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stock prices over time

Constraint

Must cooldown one day after selling

Output

Maximum profit achievable

Key Takeaway

🎯 Key Insight: Model as state machine with three states: holding, sold (cooldown), and resting

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is modeling this as a state machine with three states: holding stock, just sold (cooldown), and resting. Best approach is Dynamic Programming with state transitions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(3ⁿ)	O(n)	Try all possible buy/sell/rest combinations recursively
Memoized Recursion	O(n)	O(n)	Cache results for (day, holding_status) to avoid repeated calculations
Dynamic Programming (State Machine)	O(n)	O(1)	Track three states: held, sold (cooldown), and rest using iterative DP

Recursive Brute Force — Algorithm Steps

For each day, try all valid actions
Recursively calculate profit for remaining days
Return maximum profit across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Day 0

Can buy at price 1 or rest

Branch Decisions

Each choice leads to new subproblems

Exponential Growth

Tree grows exponentially with repeated work

Code -

solution.c — C

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

int backtrack(int* prices, int len, int day, int holding) {
    if (day >= len) {
        return 0;
    }
    
    int maxProfit = 0;
    
    if (holding) {
        // Sell today (then must cooldown tomorrow)
        int profit = prices[day] + backtrack(prices, len, day + 2, 0);
        if (profit > maxProfit) maxProfit = profit;
        // Hold (don't sell)
        profit = backtrack(prices, len, day + 1, 1);
        if (profit > maxProfit) maxProfit = profit;
    } else {
        // Buy today
        int profit = -prices[day] + backtrack(prices, len, day + 1, 1);
        if (profit > maxProfit) maxProfit = profit;
        // Rest (don't buy)
        profit = backtrack(prices, len, day + 1, 0);
        if (profit > maxProfit) maxProfit = profit;
    }
    
    return maxProfit;
}

int solution(int* prices, int len) {
    return backtrack(prices, len, 0, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000];
    int len = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[len++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(prices, len);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

Each day has up to 3 choices, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals array length

⚡ Linearithmic Space

156.0K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler