Best Time - 2 Transactions

▶

Steps

setup

Initialize profit and maxDiff arrays

Initialize profit array with zeros and maxDiff array with -prices[0] for all transaction counts (0 to 2). This sets the base state before processing days.

💡 Starting with zero profit and maxDiff as negative first price models the initial buying cost for each transaction count.

Line:

profit = [0] * 3
maxDiff = [-prices[0]] * 3

💡 Initial arrays represent no profit and the cost of buying on day 0 for each transaction count.

fill_cells

Start day 1 iteration (price=3), update for k=2

For day 1 (price=3), update profit[2] by comparing current profit[2] and price + maxDiff[2]. Then update maxDiff[2] using profit[1] - price.

💡 Updating profit and maxDiff for highest transaction count first ensures dependencies on lower counts are preserved.

Line:

profit[2] = max(profit[2], prices[1] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[1])

💡 No profit improvement for 2 transactions on day 1; maxDiff remains same as no better buying opportunity found.

fill_cells

Day 1 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 1 price=3 similarly: profit[1] = max(profit[1], price + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - price).

💡 Lower transaction counts update after higher ones to maintain correct dependency order.

Line:

profit[1] = max(profit[1], prices[1] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[1])

💡 No profit improvement for 1 transaction on day 1; maxDiff unchanged.

fill_cells

Day 2 iteration (price=5), update for k=2

For day 2 price=5, update profit[2] = max(profit[2], 5 + maxDiff[2]) and maxDiff[2] = max(maxDiff[2], profit[1] - 5).

💡 Higher price may increase profit by selling today; maxDiff updates track better buy opportunities.

Line:

profit[2] = max(profit[2], prices[2] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[2])

💡 Profit for 2 transactions improves to 2 by selling at price 5 after buying at price 3.

fill_cells

Day 2 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 2 price=5: profit[1] = max(profit[1], 5 + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - 5).

💡 Check if selling today improves profit for 1 transaction.

Line:

profit[1] = max(profit[1], prices[2] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[2])

💡 Profit for 1 transaction improves to 2 by selling at price 5.

fill_cells

Day 3 iteration (price=0), update for k=2

For day 3 price=0, update profit[2] and maxDiff[2]: profit[2] = max(profit[2], 0 + maxDiff[2]), maxDiff[2] = max(maxDiff[2], profit[1] - 0).

💡 Low price may improve maxDiff by representing a better buying opportunity.

Line:

profit[2] = max(profit[2], prices[3] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[3])

💡 maxDiff[2] updates to 2, indicating a better buy opportunity after 1 transaction profit of 2.

fill_cells

Day 3 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 3 price=0: profit[1] = max(profit[1], 0 + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - 0).

💡 Low price may improve maxDiff for 1 transaction.

Line:

profit[1] = max(profit[1], prices[3] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[3])

💡 maxDiff[1] updates to 0, better buy opportunity for 1 transaction.

fill_cells

Day 4 iteration (price=0), update for k=2

For day 4 price=0, update profit[2] and maxDiff[2]: profit[2] = max(profit[2], 0 + maxDiff[2]), maxDiff[2] = max(maxDiff[2], profit[1] - 0).

💡 Repeated low price may further improve maxDiff for 2 transactions.

Line:

profit[2] = max(profit[2], prices[4] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[4])

💡 No profit increase but maxDiff remains at best buy opportunity for 2 transactions.

fill_cells

Day 4 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 4 price=0: profit[1] = max(profit[1], 0 + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - 0).

💡 Repeated low price may improve maxDiff for 1 transaction.

Line:

profit[1] = max(profit[1], prices[4] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[4])

💡 No change in profit or maxDiff for 1 transaction.

fill_cells

Day 5 iteration (price=3), update for k=2

For day 5 price=3, update profit[2] = max(profit[2], 3 + maxDiff[2]) and maxDiff[2] = max(maxDiff[2], profit[1] - 3).

💡 Higher price may increase profit for 2 transactions by selling today.

Line:

profit[2] = max(profit[2], prices[5] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[5])

💡 Profit for 2 transactions improves to 5 by selling at price 3 after best buy opportunity.

fill_cells

Day 5 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 5 price=3: profit[1] = max(profit[1], 3 + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - 3).

💡 Check if selling today improves profit for 1 transaction.

Line:

profit[1] = max(profit[1], prices[5] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[5])

💡 Profit for 1 transaction improves to 3 by selling at price 3 after buying at price 0.

fill_cells

Day 6 iteration (price=1), update for k=2

For day 6 price=1, update profit[2] = max(profit[2], 1 + maxDiff[2]) and maxDiff[2] = max(maxDiff[2], profit[1] - 1).

💡 Lower price may improve maxDiff for 2 transactions.

Line:

profit[2] = max(profit[2], prices[6] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[6])

💡 maxDiff[2] remains 2, profit unchanged.

fill_cells

Day 6 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 6 price=1: profit[1] = max(profit[1], 1 + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - 1).

💡 Lower price may improve maxDiff for 1 transaction.

Line:

profit[1] = max(profit[1], prices[6] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[6])

💡 No change in profit or maxDiff for 1 transaction.

fill_cells

Day 7 iteration (price=4), update for k=2

For day 7 price=4, update profit[2] = max(profit[2], 4 + maxDiff[2]) and maxDiff[2] = max(maxDiff[2], profit[1] - 4).

💡 Higher price may increase profit for 2 transactions by selling today.

Line:

profit[2] = max(profit[2], prices[7] + maxDiff[2])
maxDiff[2] = max(maxDiff[2], profit[1] - prices[7])

💡 Profit for 2 transactions improves to 6 by selling at price 4 after best buy opportunity.

fill_cells

Day 7 iteration, update for k=1

Update profit[1] and maxDiff[1] for day 7 price=4: profit[1] = max(profit[1], 4 + maxDiff[1]), maxDiff[1] = max(maxDiff[1], profit[0] - 4).

💡 Check if selling today improves profit for 1 transaction.

Line:

profit[1] = max(profit[1], prices[7] + maxDiff[1])
maxDiff[1] = max(maxDiff[1], profit[0] - prices[7])

💡 Profit for 1 transaction improves to 4 by selling at price 4.

reconstruct

Return final profit for 2 transactions

After processing all days, return profit[2] which holds the maximum profit achievable with up to 2 transactions.

💡 The final profit value is the answer to the problem.

Line:

return profit[2]

💡 The algorithm successfully computed the maximum profit of 6 for two transactions.

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    profit = [0] * 3  # STEP 1
    maxDiff = [-prices[0]] * 3  # STEP 1
    for i in range(1, n):  # STEP 2-15
        for k in range(2, 0, -1):
            profit[k] = max(profit[k], prices[i] + maxDiff[k])  # STEP update profit
            maxDiff[k] = max(maxDiff[k], profit[k-1] - prices[i])  # STEP update maxDiff
    return profit[2]  # STEP 16

if __name__ == '__main__':
    prices = [3,3,5,0,0,3,1,4]
    print(maxProfit(prices))  # Expected output: 6

📊

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

Watching each update to profit and maxDiff arrays reveals how the algorithm balances buying and selling decisions over time to maximize total profit.

Item 0 - wt:3 val:0

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

profit[0] = 0

Item 1 - wt:3 val:0

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

profit[2] updated

Item 1 - wt:3 val:0

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

profit[1] updated

Item 2 - wt:5 val:2

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

profit[2] updated to 2

Item 2 - wt:5 val:2

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

profit[1] updated to 2

Item 3 - wt:0 val:2

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

maxDiff[2] updated to 2

Item 3 - wt:0 val:2

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

maxDiff[1] updated to 0

Item 4 - wt:0 val:2

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

profit[2] unchanged

Item 4 - wt:0 val:2

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

profit[1] unchanged

Item 5 - wt:3 val:5

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

profit[2] updated to 5

Item 5 - wt:3 val:5

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

profit[1] updated to 3

Item 6 - wt:1 val:5

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

maxDiff[2] unchanged

Item 6 - wt:1 val:5

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

profit[1] unchanged

Item 7 - wt:4 val:6

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

profit[2] updated to 6

Item 7 - wt:4 val:6

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

profit[1] updated to 4

Item 7 - wt:4 val:6

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

final profit[2] = 6

Key Takeaways

✓ The algorithm maintains two arrays, profit and maxDiff, to track the best profits and buying opportunities for each transaction count.

This separation clarifies how buying and selling decisions are optimized independently but combined to maximize profit.

✓ Updating transaction counts in reverse order (from 2 down to 1) preserves dependencies on previous transaction profits.

This order ensures that maxDiff uses the correct profit values from the previous transaction count.

✓ maxDiff array captures the best net cost of buying considering profits from previous transactions, enabling efficient profit updates.

This insight is hard to see from code alone but becomes clear when watching maxDiff values update step-by-step.

Practice

1. 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

2. 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

3. Given the following code for the Jump Game II problem, what is the value of the variable jumps returned when the input is [2,1,1]?

easy

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Trace variables for input [2,1,1]

   n=3, loop i in [0,1]. - i=0: furthest = max(0, 0+2) = 2; i == current_end (0), so jumps = 1, current_end = 2 - i=1: furthest = max(2, 1+1) = 2; i != current_end (2), no jump increment Loop ends.

2. Step 2: Return jumps

   jumps = 1 is returned, meaning minimum 1 jump to reach the end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   One jump from index 0 to last index covers entire array [OK]

Hint: Increment jumps only when i reaches current_end [OK]

Common Mistakes:

• Incrementing jumps too early or too late
• Off-by-one errors in loop range
• Misunderstanding when to update current_end

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. The following code attempts to solve the Word Break problem. Identify the line that contains a subtle bug that can cause incorrect results or inefficiency.

medium

A. Line 5: Incorrect base case initialization

B. Line 1: Using list instead of set for word lookup

C. Line 8: Incorrect substring indices

D. Line 9: Setting dp[i] to True without checking all lengths

Solution

1. Step 1: Analyze data structure for word lookup

   Using a list for word_set causes substring membership checks to be O(n) instead of O(1), leading to inefficiency and possible timeouts.

2. Step 2: Verify other lines

   Base case dp[0] = True is correct; substring indices are correct; missing break after dp[i] = True causes inefficiency but not incorrectness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   List lookup is linear, set lookup is constant time [OK]

Hint: Use set for O(1) membership, not list [OK]

Common Mistakes:

• Forgetting to break inner loop
• Misindexing substring
• Incorrect base case initialization