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

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

✓ Dynamic Programming (State Machine)

⏱️ Time: O(n) Space: O(1)

Model as state machine with three states: holding stock, just sold (cooldown required), or resting. For each day, update all possible states based on valid transitions.

Memoized Recursion

⏱️ Time: O(n) Space: O(n)

Same recursive approach but store results in a memo table indexed by day and holding status. This eliminates redundant subproblem calculations.

Recursive Brute Force

⏱️ Time: O(3ⁿ) Space: O(n)

For each day, recursively explore all valid actions: buy (if not holding), sell (if holding), or rest. The cooldown constraint means after selling, we must skip the next day.

Dynamic Programming (State Machine) — Algorithm Steps

Define three states: held, sold, rest
For each day, update states based on transitions
Return maximum of sold and rest states

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize States

Start with held=-price[0], sold=0, rest=0

State Transitions

Update each state based on valid actions

Final Result

Maximum of sold and rest states

Code -

solution.c — C

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

int solution(int* prices, int len) {
    if (len == 0) {
        return 0;
    }
    
    // States: held (own stock), sold (just sold, cooldown), rest (can buy)
    int held = -prices[0];  // Buy on day 0
    int sold = 0;           // Can't sell on day 0
    int rest = 0;           // Start with no action
    
    for (int i = 1; i < len; i++) {
        int prevHeld = held;
        int prevSold = sold;
        int prevRest = rest;
        
        // Update states based on valid transitions
        int buyToday = prevRest - prices[i];
        held = (prevHeld > buyToday) ? prevHeld : buyToday;  // Keep holding or buy today
        sold = prevHeld + prices[i];                         // Sell today (must have been holding)
        rest = (prevRest > prevSold) ? prevRest : prevSold;  // Keep resting or end cooldown
    }
    
    return (sold > rest) ? sold : rest;  // Don't end while holding stock
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    if (strstr(line, "[]") != NULL) {
        printf("0\n");
        return 0;
    }
    
    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(n)

Single pass through array, constant work per day

✓ Linear Growth

Space Complexity

O(1)

Only three variables to track current states

⚡ 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

Best Time to Buy and Sell Stock with Cooldown - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming (State Machine) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler