Breaking Down Stock Trading DP

Worked through three stock trading problems today. Interesting how the same base problem changes completely depending on the constraints.

121. Best Time to Buy and Sell Stock

LeetCode 121 →

One buy, one sell. Find the max profit.

The key insight — track the minimum price seen so far, and at each day check if selling today gives a better profit.

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
 
    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
 
    return max_profit

Can also think of it as Two Pointer — left stays at the cheapest day, right moves forward. If right < left, move left to right.

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

122. Best Time to Buy and Sell Stock II

LeetCode 122 →

Now you can buy and sell as many times as you want.

If you can trade every day, the answer is simple — just take every upward move. That's Greedy.

def maxProfit(prices):
    max_profit = 0
 
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
 
    return max_profit

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

Same base problem as 121, but removing the "one trade only" constraint completely changes the approach — from Two Pointer to Greedy.

309. Best Time to Buy and Sell Stock with Cooldown

LeetCode 309 →

Multiple trades allowed, but after selling you have to wait one day before buying again.

Greedy doesn't work here because selling today affects what you can do the day after. So we need DP.

Method 1: Memoization (Top-down DP)

Think of it as a decision tree. At each day, you either buy, sell, or do nothing. The state is (index, can_buy).

def maxProfit(prices):
    dp = {}
 
    def dfs(i, availability):
        if i >= len(prices):
            return 0
        if (i, availability) in dp:
            return dp[(i, availability)]
 
        cooldown = dfs(i + 1, availability)
 
        if availability:
            buy = dfs(i + 1, False) - prices[i]
            dp[(i, availability)] = max(cooldown, buy)
        else:
            sell = dfs(i + 2, True) + prices[i]
            dp[(i, availability)] = max(sell, cooldown)
 
        return dp[(i, availability)]
 
    return dfs(0, True)

The cooldown is handled by jumping to i + 2 when selling — skipping the next day entirely.

Why memoization works: The state (i, availability) has n × 2 possible combinations. Once computed, each state is cached in dp and never recalculated.

Time: O(n) / Space: O(n)

Method 2: Bottom-up DP (State Machine)

Instead of recursion, track three states at every day:

• holding — currently holding a stock
• sold — sold today
• idle — doing nothing (resting or in cooldown)

def maxProfit(prices):
    holding = -prices[0]
    sold = 0
    idle = 0
 
    for i in range(1, len(prices)):
        prev_holding = holding
        prev_sold = sold
        prev_idle = idle
 
        holding = max(prev_holding, prev_idle - prices[i])
        sold = prev_holding + prices[i]
        idle = max(prev_idle, prev_sold)
 
    return max(sold, idle)

State transitions:

• holding → keep holding OR buy from idle
• sold → sell from holding
• idle → stay idle OR cooldown from sold (this is where cooldown is enforced)

The prev_ variables are necessary because all three states update simultaneously — without them, an updated value would bleed into the next calculation in the same loop.

return max(sold, idle) — holding is excluded because unrealized profit doesn't count. You have to actually sell to lock in the gain.

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

Which one to use in interviews?

Both are worth knowing. A good flow:

1. Start with memoization — the logic is clearer and easier to explain
2. Then optimize to bottom-up DP — better space complexity (O(n) → O(1))

Pattern

Same base problem, different constraints → different approach: