#113 Medium Time O(n) Space O(1) Animated

Best Time to Buy and Sell Stock with Cooldown

Maximize profit with cooldown period between sell and buy.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Two-dimensional dynamic programming

A table exposes how two changing prefixes or positions depend on smaller cases.

Approach: Dynamic Programming (State Machine)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

A table exposes how two changing prefixes or positions depend on smaller cases.

Common Pitfall

Initialize the first row and column before using neighboring cells.

Description

Maximize profit with cooldown period between sell and buy.

Constraints

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

Solution — Dynamic Programming (State Machine)

TimeO(n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Define the row and column meaning.
Initialize base cases.
Fill cells in dependency order.
Read the answer from the target cell.

def maxProfit(prices):
    dp = {} # key=(i, buying) val=max_profit
    def dfs(i, buying):
        if i >= len(prices):
            return 0
        if (i, buying) in dp:
            return dp[(i, buying)]
            
        if buying:
            buy = dfs(i + 1, not buying) - prices[i]
            cooldown = dfs(i + 1, buying)
            dp[(i, buying)] = max(buy, cooldown)
        else:
            sell = dfs(i + 2, not buying) + prices[i]
            cooldown = dfs(i + 1, buying)
            dp[(i, buying)] = max(sell, cooldown)
            
        return dp[(i, buying)]
        
    return dfs(0, True)

Longest Common Subsequence

Coin Change II

Best Time to Buy and Sell Stock with Cooldown

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (State Machine)