Best Time to Buy Sell IV (K Transactions)

▶

Steps

setup

Initialize DP arrays

We create two 2D arrays, next_dp and curr_dp, each sized (k+1) x 2, initialized to zero. These arrays will hold the max profit states for each transaction count and holding state.

💡 Initializing these arrays to zero sets the base case: no profit when no days or transactions remain.

Line:

next_dp = [[0, 0] for _ in range(k + 1)]
curr_dp = [[0, 0] for _ in range(k + 1)]

💡 DP arrays represent profit states for all transaction counts and holding states at the next day.

traverse

Start iterating days backwards: i = 5

We start processing from the last day (index 5, price=3). We will update curr_dp for each transaction count t from 1 to k.

💡 Processing days backwards allows us to use next_dp (future day) states to compute current day states.

Line:

for i in range(n - 1, -1, -1):

💡 The iteration order is crucial to build the solution from the end to the start.

fill_cells

Update curr_dp for t=1, holding=0 (not holding stock)

For transaction count t=1 and holding=0, we decide whether to buy stock today or skip. We compute max(-prices[5] + next_dp[1][1], next_dp[1][0]) = max(-3 + 0, 0) = 0.

💡 This step shows the choice between buying stock today or doing nothing, using future profits.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Buying today is not profitable here, so skipping yields zero profit.

fill_cells

Update curr_dp for t=1, holding=1 (holding stock)

For t=1 and holding=1, decide whether to sell stock today or skip. Compute max(prices[5] + next_dp[0][0], next_dp[1][1]) = max(3 + 0, 0) = 3.

💡 This step shows the choice to sell stock today or hold it, using profits from fewer transactions left.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Selling today yields profit 3, better than skipping.

fill_cells

Update curr_dp for t=2, holding=0 (not holding stock)

For t=2 and holding=0, decide to buy or skip. max(-prices[5] + next_dp[2][1], next_dp[2][0]) = max(-3 + 0, 0) = 0.

💡 Same logic applies for higher transaction counts, showing buying or skipping.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Buying today is not profitable, skipping yields zero.

fill_cells

Update curr_dp for t=2, holding=1 (holding stock)

For t=2 and holding=1, decide to sell or skip. max(prices[5] + next_dp[1][0], next_dp[2][1]) = max(3 + 0, 0) = 3.

💡 Selling stock at this transaction count yields profit 3.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Selling converts holding state to profit.

expand

Swap curr_dp and next_dp after day 5

After processing day 5, we swap curr_dp and next_dp so next_dp holds the updated states for the next iteration.

💡 Swapping arrays avoids extra copying and prepares for the next day iteration.

Line:

next_dp, curr_dp = curr_dp, next_dp

💡 The updated states become the reference for the previous day.

fill_cells

Iterate day i=4 (price=0), update t=1 holding=0

At day 4, t=1, holding=0, decide to buy or skip: max(-0 + next_dp[1][1], next_dp[1][0]) = max(0 + 3, 0) = 3.

💡 Buying at price 0 plus future profit is better than skipping.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Buying at low price sets up for future profit.

fill_cells

Update day 4, t=1, holding=1

Decide to sell or skip: max(prices[4] + next_dp[0][0], next_dp[1][1]) = max(0 + 0, 3) = 3.

💡 Selling now yields no profit, skipping keeps profit 3.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Sometimes skipping is better than selling at low price.

fill_cells

Update day 4, t=2, holding=0

Decide to buy or skip: max(-0 + next_dp[2][1], next_dp[2][0]) = max(0 + 3, 0) = 3.

💡 Buying at zero price with 2 transactions left is profitable.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Buying low sets up for future profit with remaining transactions.

fill_cells

Update day 4, t=2, holding=1

Decide to sell or skip: max(prices[4] + next_dp[1][0], next_dp[2][1]) = max(0 + 3, 3) = 3.

💡 Selling now or skipping both yield profit 3.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Sometimes selling or holding yields same profit.

expand

Swap curr_dp and next_dp after day 4

We swap curr_dp and next_dp to prepare for processing day 3.

💡 Swapping updates the reference DP arrays for the next iteration.

Line:

next_dp, curr_dp = curr_dp, next_dp

💡 DP states propagate backwards day by day.

fill_cells

Iterate day i=3 (price=5), update t=1 holding=0

At day 3, t=1, holding=0, decide to buy or skip: max(-5 + next_dp[1][1], next_dp[1][0]) = max(-5 + 3, 3) = 3.

💡 Buying at price 5 is less profitable than skipping.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Sometimes skipping is better than buying at high price.

fill_cells

Update day 3, t=1, holding=1

Decide to sell or skip: max(prices[3] + next_dp[0][0], next_dp[1][1]) = max(5 + 0, 3) = 5.

💡 Selling at price 5 yields profit 5, better than skipping.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Selling at a high price increases profit.

fill_cells

Update day 3, t=2, holding=0

Decide to buy or skip: max(-5 + next_dp[2][1], next_dp[2][0]) = max(-5 + 3, 3) = 3.

💡 Buying at price 5 is less profitable than skipping.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Skipping is better than buying at high price.

fill_cells

Update day 3, t=2, holding=1

Decide to sell or skip: max(prices[3] + next_dp[1][0], next_dp[2][1]) = max(5 + 3, 3) = 8.

💡 Selling now yields profit 8, combining previous profits.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Selling at this point maximizes profit with 2 transactions.

expand

Swap curr_dp and next_dp after day 3

Swap curr_dp and next_dp to update states for day 2 iteration.

💡 Swapping prepares DP arrays for next iteration.

Line:

next_dp, curr_dp = curr_dp, next_dp

💡 DP states propagate backwards day by day.

fill_cells

Iterate day i=2 (price=6), update t=1 holding=0

At day 2, t=1, holding=0, decide to buy or skip: max(-6 + next_dp[1][1], next_dp[1][0]) = max(-6 + 5, 3) = 3.

💡 Buying at price 6 is less profitable than skipping.

Line:

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])

💡 Skipping is better than buying at high price.

fill_cells

Update day 2, t=1, holding=1

Decide to sell or skip: max(prices[2] + next_dp[0][0], next_dp[1][1]) = max(6 + 0, 5) = 6.

💡 Selling at price 6 yields profit 6, better than skipping.

Line:

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])

💡 Selling at high price increases profit.

reconstruct

Final swap and return answer

After processing all days, we swap one last time and return next_dp[k][0] = next_dp[2][0] = 7 as the max profit.

💡 The answer is the max profit at day 0 with k transactions and no stock held.

Line:

next_dp, curr_dp = curr_dp, next_dp
return next_dp[k][0]

💡 The DP arrays hold the final answer after all updates.

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]  # STEP 1
    curr_dp = [[0, 0] for _ in range(k + 1)]  # STEP 1
    for i in range(n - 1, -1, -1):  # STEP 2
        for t in range(1, k + 1):  # STEPS 3-6
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])  # STEP 3
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])  # STEP 4
        next_dp, curr_dp = curr_dp, next_dp  # STEP 7
    return next_dp[k][0]  # STEP 20

📊

Best Time to Buy Sell IV (K Transactions) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step helps you understand how the algorithm builds up the solution backwards in time, and how the states represent holding or not holding stock with remaining transactions.

setup

0

1

Result: 0

traverse

0

1

Result: 0

compare

0

t

1

Result: 0

compare

0

t

1

Result: 0

compare

0

1

Result: 0

compare

0

1

Result: 0

move_left

0

1

Result: 0

compare

0

t

1

Result: 0

compare

0

t

1

Result: 0

compare

0

1

Result: 0

compare

0

1

Result: 0

move_left

0

1

Result: 0

compare

0

t

1

Result: 0

compare

0

t

1

Result: 0

compare

0

1

Result: 0

compare

0

1

Result: 0

move_left

0

1

Result: 0

compare

0

t

1

Result: 0

compare

0

t

1

Result: 0

record

0

1

Result: 7

Key Takeaways

✓ The DP arrays represent the maximum profit achievable at each day, transaction count, and holding state.

This insight is hard to see from code alone because the arrays and indices abstract away the meaning of states.

✓ The algorithm processes days backwards, building solutions from the end to the start.

Visualizing the backward iteration clarifies why next_dp holds future states and curr_dp current states.

✓ At each step, the algorithm chooses between buying, selling, or skipping by comparing profits.

Seeing these decisions step-by-step reveals how the algorithm avoids bad trades and maximizes profit.

Practice

1. What is the worst-case time complexity of the put operation in the brute force LFU cache implementation that scans all keys to find the least frequently used item for eviction?

medium

A. O(1) -- constant time due to direct access

B. O(n) -- linear time scanning all keys for eviction

C. O(log n) -- due to sorting keys by frequency

D. O(n^2) -- nested scanning for frequency and recency

Solution

1. Step 1: Identify eviction process

   Eviction requires scanning all keys to find the minimum frequency, which takes O(n) time where n is the number of keys.

2. Step 2: Confirm no sorting or nested loops

   The code uses min() and list comprehensions but does not sort or nest loops over keys, so complexity is O(n), not O(log n) or O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Eviction scanning all keys -> O(n) time [OK]

Hint: Eviction scans all keys linearly -> O(n) time [OK]

Common Mistakes:

• Assuming O(1) due to hashmap
• Confusing min() with sorting
• Overestimating complexity as O(n^2)

2. Examine the following buggy code snippet for the bitmask backtracking N-Queens solution. Which line contains the subtle bug that causes incorrect pruning of valid queen placements?

medium

A. Line updating pos_diags and neg_diags with incorrect bit shifts

B. Line extracting rightmost 1-bit from available_positions

C. Line computing available_positions with bitwise negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify diagonal bitmask updates

   pos_diags should be shifted left (<< 1) and neg_diags shifted right (>> 1) after adding pos.

2. Step 2: Spot incorrect shift directions

   The code shifts pos_diags right and neg_diags left, reversing the intended diagonal tracking, causing pruning errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal shifts must match board traversal direction [OK]

Hint: Diagonal bitmask shifts must be << for pos_diags, >> for neg_diags [OK]

Common Mistakes:

• Reversing diagonal bit shifts
• Forgetting to backtrack board state
• Incorrect bitmask negation

3. What is the time complexity of the Trie-based palindrome pairs solution, given n words each of maximum length k?

medium

A. O(n^2 * k)

B. O(n * k)

C. O(n * k^2)

D. O(n^2 * k^2)

Solution

1. Step 1: Identify outer loop complexity

   We process each of the n words, so at least O(n).

2. Step 2: Analyze inner operations per word

   Adding a word to the Trie involves iterating over k characters and checking palindrome prefixes which can take O(k) each, resulting in O(k^2) per word.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie build and search combined yield O(n * k^2) time [OK]

Hint: Palindrome checks inside Trie add quadratic factor in k [OK]

Common Mistakes:

• Assuming O(n^2 * k) from brute force
• Ignoring palindrome prefix checks cost
• Confusing linear with quadratic in k

4. What is the time complexity of the optimal solution for Word Search II that uses backtracking with a Trie and in-place board modification, assuming the board size is NxM, the number of words is W, and the maximum length of a word is L?

medium

A. O(W * N * M * 4^L) because each word is searched independently

B. O(W * L) for building Trie plus O(N * M * 4^L) for backtracking

C. O(N * M * L * W) because Trie traversal multiplies word length and count

D. O(N * M * 4^L) due to backtracking pruning with Trie prefix checks

Solution

1. Step 1: Identify Trie construction cost

   Building the Trie takes O(W * L) time, inserting each word character by character.

2. Step 2: Analyze backtracking complexity

   Backtracking explores up to 4^L paths from each cell, so O(N * M * 4^L) dominates search time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie build plus backtracking combined yields O(W*L + N*M*4^L) [OK]

Hint: Trie build separate from backtracking cost [OK]

Common Mistakes:

• Confusing independent word search with Trie pruning
• Ignoring Trie build cost
• Multiplying all parameters incorrectly

5. Examine the following snippet from an implementation of the optimal Word Search II solution. Which line contains a subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line where curr_node.word is not set to null after found

B. Line where board[r][c] is set to '#'

C. Line where curr_node.word is appended to res

D. Line where backtrack is recursively called on neighbors

Solution

1. Step 1: Identify purpose of setting curr_node.word to None

   This prevents adding the same word multiple times by marking it as found.

2. Step 2: Analyze effect of missing this line

   Without setting curr_node.word to None, duplicates can be appended and redundant searches occur, possibly causing inefficiency or infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing word removal after found causes duplicates [OK]

Hint: Mark found words None to avoid duplicates [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not pruning found words
• Incorrect recursion boundaries