Best Time - Cooldown

▶

Steps

setup

Initialize variables for day 0

Set initial states for day 0: hold is negative price (buying stock), cool and free are zero (no profit yet).

💡 Initialization sets the base case for the DP states, crucial for correct subsequent updates.

Line:

hold = -prices[0]
cool = 0
free = 0

💡 Starting with hold = -1 means we consider buying on day 0, while cool and free start at zero profit.

fill_cells

Day 1: Save previous hold value

Before updating day 1 states, save previous hold value (-1) for use in cool calculation.

💡 Preserving previous hold is necessary because cool depends on it plus today's price.

Line:

prev_hold = hold

💡 We keep prev_hold = -1 to compute cool state for day 1 correctly.

fill_cells

Day 1: Update hold state

Calculate hold for day 1 as max of holding from day 0 or buying today after free state.

💡 This step models the choice to keep holding or buy today if not in cooldown.

Line:

hold = max(hold, free - prices[i])

💡 Holding from day 0 is better than buying today at price 2, so hold stays -1.

fill_cells

Day 1: Update free state

Update free state as max of previous free or cool states, representing no stock and no cooldown.

💡 Free state tracks profit when not holding and not in cooldown, so we pick the best previous profit.

Line:

free = max(free, cool)

💡 No profit yet from cooldown or free states, so free remains 0.

fill_cells

Day 1: Update cool state

Calculate cool state as previous hold plus today's price, representing selling today and entering cooldown.

💡 Selling today yields profit from previously held stock plus today's price.

Line:

cool = prev_hold + prices[i]

💡 Selling today yields profit 1, entering cooldown state.

fill_cells

Day 2: Save previous hold value

Save hold value from day 1 (-1) before updating day 2 states.

💡 Previous hold is needed to compute cool state for day 2.

Line:

prev_hold = hold

💡 prev_hold = -1 will be used to calculate cool for day 2.

fill_cells

Day 2: Update hold state

Calculate hold for day 2 as max of holding from day 1 or buying today after free state.

💡 Deciding whether to keep holding or buy today at price 3.

Line:

hold = max(hold, free - prices[i])

💡 Holding from day 1 is better than buying today at price 3.

fill_cells

Day 2: Update free state

Update free state as max of previous free or cool states.

💡 Choosing best profit when not holding and not in cooldown.

Line:

free = max(free, cool)

💡 Free state improves to 1, reflecting profit from cooldown ending.

fill_cells

Day 2: Update cool state

Calculate cool state as previous hold plus today's price.

💡 Selling today yields profit from previously held stock plus today's price.

Line:

cool = prev_hold + prices[i]

💡 Selling today yields profit 2, better than previous cooldown profit.

fill_cells

Day 3: Save previous hold value

Save hold value from day 2 (-1) before updating day 3 states.

💡 Previous hold is needed to compute cool state for day 3.

Line:

prev_hold = hold

💡 prev_hold = -1 will be used to calculate cool for day 3.

fill_cells

Day 3: Update hold state

Calculate hold for day 3 as max of holding from day 2 or buying today after free state.

💡 Deciding whether to keep holding or buy today at price 0.

Line:

hold = max(hold, free - prices[i])

💡 Buying today at price 0 after free state yields better hold profit.

fill_cells

Day 3: Update free state

Update free state as max of previous free or cool states.

💡 Choosing best profit when not holding and not in cooldown.

Line:

free = max(free, cool)

💡 Free state improves to 2, reflecting best profit so far without holding.

fill_cells

Day 3: Update cool state

Calculate cool state as previous hold plus today's price.

💡 Selling today yields profit from previously held stock plus today's price.

Line:

cool = prev_hold + prices[i]

💡 Selling today at price 0 yields less profit, so cool is -1.

fill_cells

Day 4: Save previous hold value

Save hold value from day 3 (1) before updating day 4 states.

💡 Previous hold is needed to compute cool state for day 4.

Line:

prev_hold = hold

💡 prev_hold = 1 will be used to calculate cool for day 4.

fill_cells

Day 4: Update hold state

Calculate hold for day 4 as max of holding from day 3 or buying today after free state.

💡 Deciding whether to keep holding or buy today at price 2.

Line:

hold = max(hold, free - prices[i])

💡 Keeping hold from day 3 is better than buying today at price 2.

fill_cells

Day 4: Update free state

Update free state as max of previous free or cool states.

💡 Choosing best profit when not holding and not in cooldown.

Line:

free = max(free, cool)

💡 Free state remains 2, best profit without holding.

fill_cells

Day 4: Update cool state

Calculate cool state as previous hold plus today's price.

💡 Selling today yields profit from previously held stock plus today's price.

Line:

cool = prev_hold + prices[i]

💡 Selling today yields max profit 3, best so far.

reconstruct

Return final answer

Return the maximum profit on the last day, max of cool and free states.

💡 The answer is the best profit achievable after all days considering cooldown.

Line:

return max(cool, free)

💡 Maximum profit is 3, achieved by selling on day 4 after cooldown.

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    hold = -prices[0]  # STEP 1
    cool = 0           # STEP 1
    free = 0           # STEP 1
    for i in range(1, n):
        prev_hold = hold  # STEP 2,6,10,14
        hold = max(hold, free - prices[i])  # STEP 3,7,11,15
        free = max(free, cool)               # STEP 4,8,12,16
        cool = prev_hold + prices[i]        # STEP 5,9,13,17
    return max(cool, free)  # STEP 18

if __name__ == '__main__':
    print(maxProfit([1,2,3,0,2]))  # 3

📊

Best Time - Cooldown - Watch the Algorithm Execute, Step by Step

Watching each state update helps you understand how cooldown affects buying and selling decisions, which is hard to grasp from code alone.

Item 0 - wt:1 val:1

i\w	0	1	2	3	4
i=0	-1	?	?	?	?
i=1	0	?	?	?	?
i=2	0	?	?	?	?

hold = -1

Item 1 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	?	?	?	?
i=1	0	?	?	?	?
i=2	0	?	?	?	?

prev_hold = -1

Item 1 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	?	?	?
i=1	0	?	?	?	?
i=2	0	?	?	?	?

hold = -1

Item 1 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	?	?	?
i=1	0	?	?	?	?
i=2	0	0	?	?	?

free = 0

Item 1 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	?	?	?
i=1	0	1	?	?	?
i=2	0	0	?	?	?

cool = 1

Item 2 - wt:3 val:3

i\w	0	1	2	3	4
i=0	-1	-1	?	?	?
i=1	0	1	?	?	?
i=2	0	0	?	?	?

prev_hold = -1

Item 2 - wt:3 val:3

i\w	0	1	2	3	4
i=0	-1	-1	-1	?	?
i=1	0	1	?	?	?
i=2	0	0	?	?	?

hold = -1

Item 2 - wt:3 val:3

i\w	0	1	2	3	4
i=0	-1	-1	-1	?	?
i=1	0	1	?	?	?
i=2	0	0	1	?	?

free = 1

Item 2 - wt:3 val:3

i\w	0	1	2	3	4
i=0	-1	-1	-1	?	?
i=1	0	1	2	?	?
i=2	0	0	1	?	?

cool = 2

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0	-1	-1	-1	?	?
i=1	0	1	2	?	?
i=2	0	0	1	?	?

prev_hold = -1

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	?
i=1	0	1	2	?	?
i=2	0	0	1	?	?

hold = 1

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	?
i=1	0	1	2	?	?
i=2	0	0	1	2	?

free = 2

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	?
i=1	0	1	2	-1	?
i=2	0	0	1	2	?

cool = -1

Item 4 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	?
i=1	0	1	2	-1	?
i=2	0	0	1	2	?

prev_hold = 1

Item 4 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	1
i=1	0	1	2	-1	?
i=2	0	0	1	2	?

hold = 1

Item 4 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	1
i=1	0	1	2	-1	?
i=2	0	0	1	2	2

free = 2

Item 4 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	1
i=1	0	1	2	-1	3
i=2	0	0	1	2	2

cool = 3

Item 4 - wt:2 val:2

i\w	0	1	2	3	4
i=0	-1	-1	-1	1	1
i=1	0	1	2	-1	3
i=2	0	0	1	2	2

answer = 3

Key Takeaways

✓ Tracking three states (hold, cool, free) models the cooldown constraint elegantly.

This insight is hard to see from code alone because the states represent abstract conditions rather than explicit actions.

✓ Each day's states depend only on the previous day's states, enabling a space-optimized DP solution.

Visualizing dependencies clarifies why only a few variables are needed instead of large DP tables.

✓ Decisions to buy, sell, or cooldown are reflected in max operations updating hold, cool, and free states.

Seeing the max comparisons step-by-step reveals how the algorithm chooses the optimal action each day.

Practice

1. You are given a list of daily stock prices and want to maximize profit by buying and selling any number of times, but you cannot hold more than one stock at a time. Which algorithmic approach guarantees the optimal solution for this problem?

easy

A. Greedy approach summing all positive price differences between consecutive days

B. Dynamic Programming using a state machine to track holding and not holding states

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Divide and conquer by splitting the price array and merging results

Solution

1. Step 1: Understand problem constraints

   The problem allows unlimited transactions but only one stock can be held at a time.

2. Step 2: Identify suitable algorithm

   For this problem, the greedy approach of summing all positive price differences between consecutive days guarantees the optimal profit. This works because any profitable transaction can be decomposed into these increments.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy summing positive differences is optimal for unlimited transactions without cooldown or fees [OK]

Hint: Sum all positive price differences between consecutive days to get max profit [OK]

Common Mistakes:

• Assuming DP is required when greedy suffices
• Using brute force without memoization
• Trying divide and conquer without state tracking

2. You are given a string of digits representing an encoded message where 'A' = 1, 'B' = 2, ..., 'Z' = 26. You need to find the total number of ways to decode the message. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Dynamic programming that builds the count of decodings using previous results

B. Sorting the digits and counting unique permutations

C. Depth-first search without memoization exploring all decoding paths

D. Greedy algorithm that picks the largest valid two-digit number at each step

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all valid decodings, which can overlap and depend on previous computations.

2. Step 2: Identify suitable algorithm

   Dynamic programming efficiently counts ways by reusing previous results, avoiding exponential recomputation unlike naive DFS, and greedy or sorting approaches do not guarantee correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and optimal substructure [OK]

Hint: Count ways using previous results, not greedy or brute force [OK]

Common Mistakes:

• Thinking greedy or sorting solves decoding count correctly

3. Consider the following buggy code snippet for maxProfit. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line with 'if k >= n // 2:' condition

B. Line with 'for j in range(1, k + 1):' loop iterating forwards

C. Line initializing buy array with -float('inf')

D. Line returning sell[k] at the end

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates forwards from 1 to k, which causes buy[j] to use updated sell[j-1] from the same iteration, corrupting state.

2. Step 2: Correct iteration order

   Iterating backwards from k down to 1 prevents premature overwriting of states, preserving correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Forward iteration overwrites dp states too early [OK]

Hint: Inner loop must run backwards to avoid state overwrite [OK]

Common Mistakes:

• Forgetting to iterate backwards in space optimized DP

4. Suppose the House Robber problem is modified so you can rob the same house multiple times (unlimited reuse). Which of the following changes to the algorithm correctly computes the maximum amount you can rob?

hard

A. Use the original DP but allow robbing adjacent houses since reuse is allowed

B. Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement

C. Use a new DP where dp[i] = max(dp[i-1], dp[i-2] + nums[i]) but allow revisiting dp[i] multiple times

D. Modify DP to consider robbing the current house plus the best solution including the current house again (i.e., dp[i] = max(dp[i-1], dp[i] + nums[i]))

Solution

1. Step 1: Understand problem change

   Allowing unlimited reuse means we can rob the same house multiple times, similar to unbounded knapsack.

2. Step 2: Identify correct DP formulation

   Unbounded knapsack style DP updates dp[i] considering dp[i - 1] + nums[i] repeatedly until stable.

3. Step 3: Evaluate options

   Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement correctly describes iterative updates until no improvement, matching unbounded knapsack logic.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Original adjacency constraints no longer apply; unbounded knapsack DP fits [OK]

Hint: Reuse means unbounded knapsack, not original adjacency DP [OK]

Common Mistakes:

• Trying to reuse original adjacency DP
• Ignoring repeated state updates

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Change dp array to store counts of ways to segment instead of booleans

B. No change needed; the original DP already supports unlimited reuse of words

C. Remove the break statement after setting dp[i] = True to consider all segmentations

D. Use a recursive backtracking approach without memoization to explore all reuse possibilities

Solution

1. Step 1: Understand the reuse requirement

   Unlimited reuse means counting all possible segmentations, not just checking existence.

2. Step 2: Modify DP to count ways

   Change dp from boolean to integer counts, summing counts from dp[i - length] when substring is in dictionary.

3. Step 3: Evaluate other options

   Original DP only checks existence (boolean), removing break doesn't count ways correctly, recursion without memoization is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting ways requires dp to store counts, not booleans [OK]

Hint: Counting segmentations requires dp to store counts, not booleans [OK]

Common Mistakes:

• Assuming original DP counts ways
• Removing break to count ways incorrectly
• Using naive recursion without memoization