Best Time - Unlimited Transactions

▶

Steps

setup

Initialize states for day 0

Set initial profit for not holding stock to 0 and holding stock to negative price of day 0 (7).

💡 This sets the base case: no profit if not holding, and cost of buying stock if holding on day 0.

Line:

not_holding = 0
holding = -prices[0]

💡 Initial states represent starting conditions before any transactions.

fill_cells

Day 1: Save previous not holding state

Store previous not holding profit (0) before updating states for day 1 (price=1).

💡 We need previous not holding value to calculate new holding state after possible buy.

Line:

prev_not_holding = not_holding

💡 Preserving previous state is essential for correct state transitions.

fill_cells

Day 1: Update not holding state

Calculate max profit for not holding on day 1: max of previous not holding (0) or selling stock today (holding + price = -7 + 1 = -6).

💡 We decide whether to keep not holding or sell stock today for better profit.

Line:

not_holding = max(not_holding, holding + prices[i])

💡 Selling today is worse than doing nothing, so profit stays 0.

fill_cells

Day 1: Update holding state

Calculate max profit for holding on day 1: max of previous holding (-7) or buying today (prev_not_holding - price = 0 - 1 = -1).

💡 We decide whether to keep holding or buy stock today for better profit.

Line:

holding = max(holding, prev_not_holding - prices[i])

💡 Buying at price 1 is better than holding from day 0 at price 7.

fill_cells

Day 2: Save previous not holding state

Store previous not holding profit (0) before updating states for day 2 (price=5).

💡 Preserving previous not holding state is necessary for correct holding update.

Line:

prev_not_holding = not_holding

💡 State preservation enables correct state transitions.

fill_cells

Day 2: Update not holding state

Calculate max profit for not holding on day 2: max of previous not holding (0) or selling today (holding + price = -1 + 5 = 4).

💡 Deciding whether to sell stock today for profit or keep not holding.

Line:

not_holding = max(not_holding, holding + prices[i])

💡 Selling today yields profit 4, better than doing nothing.

fill_cells

Day 2: Update holding state

Calculate max profit for holding on day 2: max of previous holding (-1) or buying today (prev_not_holding - price = 0 - 5 = -5).

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

Line:

holding = max(holding, prev_not_holding - prices[i])

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

fill_cells

Day 3: Save previous not holding state

Store previous not holding profit (4) before updating states for day 3 (price=3).

💡 Preserving previous not holding state is necessary for correct holding update.

Line:

prev_not_holding = not_holding

💡 State preservation enables correct state transitions.

fill_cells

Day 3: Update not holding state

Calculate max profit for not holding on day 3: max of previous not holding (4) or selling today (holding + price = -1 + 3 = 2).

💡 Deciding whether to sell stock today or keep previous profit.

Line:

not_holding = max(not_holding, holding + prices[i])

💡 Selling today yields less profit than previous not holding state.

fill_cells

Day 3: Update holding state

Calculate max profit for holding on day 3: max of previous holding (-1) or buying today (prev_not_holding - price = 4 - 3 = 1).

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

Line:

holding = max(holding, prev_not_holding - prices[i])

💡 Buying today at price 3 after profit 4 is better than holding from before.

fill_cells

Day 4: Save previous not holding state

Store previous not holding profit (4) before updating states for day 4 (price=6).

💡 Preserving previous not holding state is necessary for correct holding update.

Line:

prev_not_holding = not_holding

💡 State preservation enables correct state transitions.

fill_cells

Day 4: Update not holding state

Calculate max profit for not holding on day 4: max of previous not holding (4) or selling today (holding + price = 1 + 6 = 7).

💡 Deciding whether to sell stock today or keep previous profit.

Line:

not_holding = max(not_holding, holding + prices[i])

💡 Selling today yields higher profit than previous not holding state.

fill_cells

Day 4: Update holding state

Calculate max profit for holding on day 4: max of previous holding (1) or buying today (prev_not_holding - price = 4 - 6 = -2).

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

Line:

holding = max(holding, prev_not_holding - prices[i])

💡 Holding from before is better than buying today at higher price.

fill_cells

Day 5: Save previous not holding state

Store previous not holding profit (7) before updating states for day 5 (price=4).

💡 Preserving previous not holding state is necessary for correct holding update.

Line:

prev_not_holding = not_holding

💡 State preservation enables correct state transitions.

fill_cells

Day 5: Update not holding state

Calculate max profit for not holding on day 5: max of previous not holding (7) or selling today (holding + price = 1 + 4 = 5).

💡 Deciding whether to sell stock today or keep previous profit.

Line:

not_holding = max(not_holding, holding + prices[i])

💡 Selling today yields less profit than previous not holding state.

fill_cells

Day 5: Update holding state

Calculate max profit for holding on day 5: max of previous holding (1) or buying today (prev_not_holding - price = 7 - 4 = 3).

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

Line:

holding = max(holding, prev_not_holding - prices[i])

💡 Buying today at price 4 after profit 7 is better than holding from before.

reconstruct

Return final answer

Return the maximum profit achievable by not holding stock after the last day, which is 7.

💡 The final not holding state contains the answer to the problem.

Line:

return not_holding

💡 Maximum profit is 7, achieved by multiple buy/sell transactions.

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

if __name__ == '__main__':
    print(maxProfit([7,1,5,3,6,4]))  # 7

📊

Best Time - Unlimited Transactions - Watch the Algorithm Execute, Step by Step

Watching each update to holding and not holding states reveals how the algorithm decides when to buy or sell for maximum profit.

Item 0 - wt:7 val:0

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

not holding = 0

Item 1 - wt:1 val:0

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

prev_not_holding = 0

Item 1 - wt:1 val:0

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

not holding = 0

Item 1 - wt:1 val:-1

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

holding = -1

Item 2 - wt:5 val:0

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

prev_not_holding = 0

Item 2 - wt:5 val:4

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

not holding = 4

Item 2 - wt:5 val:-1

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

holding = -1

Item 3 - wt:3 val:4

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

prev_not_holding = 4

Item 3 - wt:3 val:4

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

not holding = 4

Item 3 - wt:3 val:1

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

holding = 1

Item 4 - wt:6 val:4

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

prev_not_holding = 4

Item 4 - wt:6 val:7

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

not holding = 7

Item 4 - wt:6 val:1

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

holding = 1

Item 5 - wt:4 val:7

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

prev_not_holding = 7

Item 5 - wt:4 val:7

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

not holding = 7

Item 5 - wt:4 val:3

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

holding = 3

Item 5 - wt:4 val:7

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

Answer = 7

Key Takeaways

✓ Tracking two states (holding and not holding) separately models the problem as a state machine.

This insight is hard to see from code alone because the states are just variables, but visualizing them clarifies the logic.

✓ The algorithm updates states day-by-day using previous states, showing clear dependency and optimal substructure.

Seeing the stepwise updates reveals how decisions build on past results, which is less obvious in code.

✓ Decisions to buy or sell are made by comparing profits, and the visualization highlights when selling or buying is beneficial.

The trace concretely shows when the algorithm chooses to buy or sell, which helps understand the decision process.

Practice

1. You are given a list of daily stock prices and want to maximize profit by buying and selling stocks with the constraint that after selling a stock, you must wait one day before buying again. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Brute force recursion exploring all buy/sell/cooldown sequences without memoization

B. A greedy algorithm that buys at every local minimum and sells at every local maximum

C. Dynamic programming with state machine to track holding, cooldown, and free states

D. Divide and conquer splitting the price array into subproblems and merging results

Solution

1. Step 1: Understand the cooldown constraint

   The cooldown day after selling prevents immediate rebuying, which breaks greedy local min/max approaches.

2. Step 2: Recognize the need for state tracking

   Dynamic programming with states (holding, cooldown, free) models the problem accurately and efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy fails on cooldown; DP state machine handles it correctly [OK]

Hint: Cooldown requires state tracking, not greedy [OK]

Common Mistakes:

• Assuming greedy local min/max works despite cooldown
• Ignoring cooldown day after selling

2. Given the following code for minimum cost climbing stairs, what is the value of curr during the first iteration of the loop when cost = [10, 15, 20]?

easy

A. 30

B. 25

C. 20

D. 15

Solution

1. Step 1: Initialize variables

   prev2 = cost[0] = 10, prev1 = cost[1] = 15

2. Step 2: Calculate curr at i=2

   curr = cost[2] + min(prev1, prev2) = 20 + min(15, 10) = 20 + 10 = 30

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr is sum of current cost plus min of previous two costs [OK]

Hint: curr = cost[i] + min(prev1, prev2) at each iteration [OK]

Common Mistakes:

• Mixing prev1 and prev2 values
• Off-by-one errors in loop
• Returning intermediate curr instead of final min

3. What is the time complexity of the optimal solution that tracks the minimum price and maximum profit in one pass for the Best Time to Buy and Sell Stock (1 tx) problem?

medium

A. O(n) because it iterates through the prices once

B. O(n^2) because it compares all pairs of days

C. O(n log n) due to sorting or binary search involved

D. O(1) because it uses constant space

Solution

1. Step 1: Identify loop structure

   The algorithm iterates through the prices array exactly once, performing constant time operations per element.

2. Step 2: Confirm no nested loops or sorting

   There are no nested loops or sorting steps, so time complexity is linear in input size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass over n elements -> O(n) time [OK]

Hint: One loop over prices array -> O(n) time [OK]

Common Mistakes:

• Confusing space complexity with time complexity
• Assuming nested loops due to DP mention
• Thinking sorting is required

4. Consider the following buggy code for maxProfit with cooldown. Which line contains the subtle bug that causes incorrect profit calculation on some inputs?

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    hold = -prices[0]
    cool = 0
    free = 0
    for i in range(1, n):
        prev_hold = hold
        hold = max(hold, free - prices[i])
        free = max(free, cool)
        cool = hold + prices[i]  # Bug here
    return max(cool, free)

medium

A. Line assigning cool = hold + prices[i]

B. Line assigning free = max(free, cool)

C. Line assigning hold = max(hold, free - prices[i])

D. Line initializing hold = -prices[0]

Solution

1. Step 1: Identify correct cooldown update

   Cooldown profit must be previous hold plus current price (selling today), so cool = prev_hold + prices[i].

2. Step 2: Spot the bug

   Code uses current hold instead of prev_hold, which may have been updated this iteration, causing incorrect profit calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using hold instead of prev_hold breaks cooldown logic [OK]

Hint: Cooldown uses previous hold, not updated hold [OK]

Common Mistakes:

• Using current hold instead of prev_hold for cooldown
• Ignoring cooldown day after selling

5. If the problem is changed to allow unlimited transactions instead of at most two, which modification to the DP approach is correct?

hard

A. Keep the same DP with k=2 but run the loop more times

B. Use a simpler DP tracking only holding and not holding states without transaction count

C. Use the same code but reset profit and maxDiff arrays after every two transactions

D. Use brute force to check all possible transaction pairs

Solution

1. Step 1: Understand unlimited transactions impact

   With unlimited transactions, tracking transaction count is unnecessary; only holding or not holding states matter.

2. Step 2: Simplify DP states

   Use a DP that tracks max profit holding stock or not holding stock each day, allowing multiple buys and sells without limit.

3. Step 3: Reject other options

   Keeping k=2 or resetting arrays is incorrect; brute force is inefficient and unnecessary.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Unlimited transactions reduce problem to simpler state machine [OK]

Hint: Unlimited transactions remove need to track transaction count [OK]

Common Mistakes:

• Trying to reuse k=2 DP for unlimited
• Resetting DP arrays incorrectly