Best Time - K Transactions

▶

Steps

setup

Check for unlimited transactions shortcut

We check if k is large enough to allow unlimited transactions, which simplifies the problem.

💡 If k >= n/2, we can just sum all positive price differences, skipping DP.

Line:

if k >= n // 2:
    return sum(max(prices[i] - prices[i-1], 0) for i in range(1, n))

💡 This step ensures we only use DP when necessary, optimizing runtime.

setup

Initialize buy and sell arrays

Create buy and sell arrays of size k+1. buy is initialized to -inf, sell to 0.

💡 buy[j] tracks max profit after buying j-th stock, sell[j] after selling j-th stock.

Line:

buy = [-float('inf')] * (k + 1)
sell = [0] * (k + 1)

💡 Initial buy values are very negative to ensure first buy updates correctly.

fill_cells

Process price = 3 (day 1)

For price 3, update buy and sell arrays for j=2 down to 1.

💡 We try to buy or sell at this price to maximize profit for each transaction count.

Line:

for j in range(k, 0, -1):
    buy[j] = max(buy[j], sell[j-1] - price)
    sell[j] = max(sell[j], buy[j] + price)

💡 At first price, buying is better than -inf, selling remains 0.

fill_cells

Process price = 2 (day 2), update j=2

At price 2, update buy[2] and sell[2] for second transaction.

💡 We check if buying now or selling now improves profit for transaction 2.

Line:

buy[2] = max(buy[2], sell[1] - price)
sell[2] = max(sell[2], buy[2] + price)

💡 Buying at lower price 2 improves buy[2].

fill_cells

Process price = 2 (day 2), update j=1

At price 2, update buy[1] and sell[1] for first transaction.

💡 We check if buying or selling now improves profit for transaction 1.

Line:

buy[1] = max(buy[1], sell[0] - price)
sell[1] = max(sell[1], buy[1] + price)

💡 Buying at price 2 improves buy[1], selling does not increase profit yet.

fill_cells

Process price = 6 (day 3), update j=2

At price 6, update buy[2] and sell[2] for second transaction.

💡 Selling at price 6 may increase profit for transaction 2.

Line:

buy[2] = max(buy[2], sell[1] - price)
sell[2] = max(sell[2], buy[2] + price)

💡 Selling at price 6 yields profit 4 for second transaction.

fill_cells

Process price = 6 (day 3), update j=1

At price 6, update buy[1] and sell[1] for first transaction.

💡 Selling at price 6 may increase profit for first transaction.

Line:

buy[1] = max(buy[1], sell[0] - price)
sell[1] = max(sell[1], buy[1] + price)

💡 Selling at price 6 yields profit 4 for first transaction.

fill_cells

Process price = 5 (day 4), update j=2

At price 5, update buy[2] and sell[2] for second transaction.

💡 Buying at price 5 may improve buy[2].

Line:

buy[2] = max(buy[2], sell[1] - price)
sell[2] = max(sell[2], buy[2] + price)

💡 Buying at price 5 after first sell improves buy[2].

fill_cells

Process price = 5 (day 4), update j=1

At price 5, update buy[1] and sell[1] for first transaction.

💡 Buying at price 5 may improve buy[1].

Line:

buy[1] = max(buy[1], sell[0] - price)
sell[1] = max(sell[1], buy[1] + price)

💡 No improvement buying or selling at price 5 for first transaction.

fill_cells

Process price = 0 (day 5), update j=2

At price 0, update buy[2] and sell[2] for second transaction.

💡 Buying at price 0 may greatly improve buy[2].

Line:

buy[2] = max(buy[2], sell[1] - price)
sell[2] = max(sell[2], buy[2] + price)

💡 Buying at price 0 after first sell greatly improves buy[2].

fill_cells

Process price = 0 (day 5), update j=1

At price 0, update buy[1] and sell[1] for first transaction.

💡 Buying at price 0 may improve buy[1].

Line:

buy[1] = max(buy[1], sell[0] - price)
sell[1] = max(sell[1], buy[1] + price)

💡 Buying at price 0 improves buy[1].

fill_cells

Process price = 3 (day 6), update j=2

At price 3, update buy[2] and sell[2] for second transaction.

💡 Selling at price 3 may increase profit for second transaction.

Line:

buy[2] = max(buy[2], sell[1] - price)
sell[2] = max(sell[2], buy[2] + price)

💡 Selling at price 3 after buying at 0 yields profit 7 for two transactions.

fill_cells

Process price = 3 (day 6), update j=1

At price 3, update buy[1] and sell[1] for first transaction.

💡 Selling at price 3 may increase profit for first transaction.

Line:

buy[1] = max(buy[1], sell[0] - price)
sell[1] = max(sell[1], buy[1] + price)

💡 Selling at price 3 does not improve first transaction profit beyond 4.

reconstruct

Return final answer sell[k]

After processing all prices, return sell[k] which holds the max profit for k transactions.

💡 sell[k] represents max profit after completing k transactions.

Line:

return sell[k]

💡 The algorithm's final output is the maximum profit achievable.

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:  # STEP 1
        return sum(max(prices[i] - prices[i-1], 0) for i in range(1, n))
    buy = [-float('inf')] * (k + 1)  # STEP 2
    sell = [0] * (k + 1)  # STEP 2
    for price in prices:  # STEP 3-13
        for j in range(k, 0, -1):
            buy[j] = max(buy[j], sell[j-1] - price)  # STEP update buy[j]
            sell[j] = max(sell[j], buy[j] + price)  # STEP update sell[j]
    return sell[k]  # STEP 14

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

📊

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

Watching each update to buy and sell arrays clarifies how the algorithm balances buying low and selling high across multiple transactions.

Initializing dp array

i\w

Initializing dp array

i\w	0	1	2
i=0	-inf	-inf	-inf
i=1	0	0	0

buy[0] = -inf

Item 0 - wt:2 val:3

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

buy[1] updated

Item 1 - wt:2 val:2

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

buy[2] updated

Item 1 - wt:2 val:2

i\w	0	1	2
i=0	-inf	-2	-2
i=1	0	0	0

buy[1] updated

Item 2 - wt:2 val:6

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

buy[2] unchanged

Item 2 - wt:2 val:6

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

buy[1] unchanged

Item 3 - wt:2 val:5

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

buy[2] updated

Item 3 - wt:2 val:5

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

buy[1] unchanged

Item 4 - wt:2 val:0

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

buy[2] updated

Item 4 - wt:2 val:0

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

buy[1] updated

Item 5 - wt:2 val:3

i\w	0	1	2
i=0	-inf	0	4
i=1	0	4	7

buy[2] unchanged

Item 5 - wt:2 val:3

i\w	0	1	2
i=0	-inf	0	4
i=1	0	4	7

buy[1] unchanged

Item 5 - wt:2 val:3

i\w	0	1	2
i=0	-inf	0	4
i=1	0	4	7

Final answer sell[2] = 7

Key Takeaways

✓ The buy and sell arrays represent state machines tracking max profit holding or not holding stock after j transactions.

This state machine view is hard to grasp from code alone but becomes clear watching each update.

✓ Updates proceed from higher to lower transaction counts to avoid overwriting dependencies during iteration.

Seeing the reverse loop order visually clarifies why we update j from k down to 1.

✓ The final sell[k] value after processing all prices is the maximum profit achievable with k transactions.

Watching sell[k] grow step-by-step shows how the algorithm accumulates profit optimally.

Practice

1. Consider the following Python code for climbing stairs:

def climb_stairs(n):
    if n <= 1:
        return 1
    first, second = 1, 1
    for _ in range(2, n + 1):
        current = first + second
        first, second = second, current
    return second

print(climb_stairs(4))

What is the value of the variable current during the last iteration of the loop?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace variable values for n=4

   Initialize first=1, second=1. Iterations: - i=2: current=1+1=2; first=1, second=2 - i=3: current=1+2=3; first=2, second=3 - i=4: current=2+3=5; first=3, second=5

2. Step 2: Identify last iteration's current value

   The last iteration is i=4, current=5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Last current computed is 5 for n=4 [OK]

Hint: Trace loop iterations carefully to find current value [OK]

Common Mistakes:

• Confusing loop bounds and off-by-one errors
• Returning previous current instead of last

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. You are given a list of non-negative integers representing the amount of money in each house along a street. You want to maximize the total amount you can rob tonight without robbing two adjacent houses. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming that considers robbing or skipping each house to maximize total

B. A greedy algorithm that always picks the house with the maximum amount next

C. Sorting the houses by amount and picking the top half

D. Depth-first search exploring all subsets of houses

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum without robbing adjacent houses, which is a classic overlapping subproblems scenario.

2. Step 2: Identify suitable algorithm

   Dynamic programming fits because it explores choices at each house (rob or skip) and uses previous results to build optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on cases like [2,7,9,3,1], DP finds max 12 [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Greedy approach fails on non-adjacent constraints

4. What is the time complexity of the optimal space-optimized bottom-up dynamic programming solution for the decoding ways problem, and why?

medium

A. O(n) but with O(n) auxiliary space for dp array

B. O(n^2) because each position checks all previous positions

C. O(2^n) due to recursive branching without memoization

D. O(n) because each character is processed once with constant checks

Solution

1. Step 1: Analyze loop iterations

   The code iterates through the string once, processing each character exactly once.

2. Step 2: Check operations per iteration

   Each iteration performs constant time checks for single and two-digit validity, no nested loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear scan with constant work per step -> O(n) time [OK]

Hint: One pass with constant work per character -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing recursion without memoization complexity

5. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., unlimited transactions per day allowed). Which modification to the original DP solution correctly handles this variant?

hard

A. Remove the transaction fee from the sell operation since multiple transactions per day are allowed.

B. Modify the DP to allow multiple buys and sells per day by iterating over all possible transactions per day, increasing time complexity to O(n²).

C. Keep the original state machine but remove the fee subtraction on sell, and update hold and cash as usual.

D. Allow buying even if already holding stock by removing the hold state check, updating hold = max(hold, cash - price) unconditionally.

Solution

1. Step 1: Understand the variant

   Multiple transactions per day means multiple buys and sells can happen on the same day, which breaks the original assumption of one transaction per day.

2. Step 2: Analyze solution impact

   The original DP assumes at most one buy or sell per day; to handle multiple transactions per day, the DP must consider all possible transaction counts per day, increasing complexity to O(n²).

3. Step 3: Evaluate options

   Simply removing fees or allowing buys while holding leads to invalid states or incorrect profits. Only enumerating all transactions per day correctly models the problem.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling multiple transactions per day requires more complex DP with nested loops [OK]

Hint: Multiple transactions per day require enumerating all transaction counts [OK]

Common Mistakes:

• Removing fees incorrectly
• Allowing invalid states by buying while holding