House Robber II (Circular)

▶

Steps

setup

Start rob function and check input length

The algorithm begins by checking if there is only one house. Since there are three houses, it proceeds to solve two linear subproblems.

💡 This step ensures the base case is handled quickly and sets up the main logic for multiple houses.

Line:

n = len(nums)
if n == 1:
    return nums[0]

💡 The problem is split into two linear cases because the houses form a circle.

setup

Initialize rob_linear for first subproblem (houses 0 to 1)

The helper function rob_linear is called for houses from index 0 to 1 (excluding last house). Variables prev and curr are initialized to 0.

💡 Initializing prev and curr to zero sets the base for the DP iteration.

Line:

def rob_linear(nums, start, end):
    prev, curr = 0, 0

💡 prev and curr track the maximum loot excluding or including the previous house.

fill_cells

Process house 0 in first subproblem

At house 0, update prev and curr: prev becomes curr (0), curr becomes max(curr, prev + nums[0]) = max(0, 0+2) = 2.

💡 This step decides whether to rob house 0 or skip it, choosing the maximum loot.

Line:

for i in range(start, end + 1):
    prev, curr = curr, max(curr, prev + nums[i])

💡 Robbing house 0 yields more loot than skipping it.

fill_cells

Process house 1 in first subproblem

At house 1, update prev and curr: prev becomes curr (2), curr becomes max(curr, prev + nums[1]) = max(2, 2+3) = 5.

💡 This step evaluates robbing house 1 versus skipping it, updating the maximum loot accordingly.

Line:

prev, curr = curr, max(curr, prev + nums[i])

💡 Robbing house 1 after skipping house 0 yields more loot.

fill_cells

Finish first subproblem rob_linear call

The first rob_linear call returns curr = 5, the maximum loot excluding the last house.

💡 Returning curr gives the best loot for the linear subproblem.

Line:

return curr

💡 The best loot from houses 0 to 1 is 5.

setup

Initialize rob_linear for second subproblem (houses 1 to 2)

The helper function rob_linear is called for houses from index 1 to 2 (excluding first house). Variables prev and curr are reset to 0.

💡 Resetting prev and curr prepares for the second linear subproblem iteration.

Line:

prev, curr = 0, 0

💡 The second subproblem is independent and starts fresh.

fill_cells

Process house 1 in second subproblem

At house 1, update prev and curr: prev becomes curr (0), curr becomes max(curr, prev + nums[1]) = max(0, 0+3) = 3.

💡 Deciding whether to rob house 1 or skip it in the second subproblem.

Line:

prev, curr = curr, max(curr, prev + nums[i])

💡 Robbing house 1 yields more loot than skipping it here as well.

fill_cells

Process house 2 in second subproblem

At house 2, update prev and curr: prev becomes curr (3), curr becomes max(curr, prev + nums[2]) = max(3, 3+2) = 5.

💡 Evaluating robbing house 2 or skipping it to maximize loot.

Line:

prev, curr = curr, max(curr, prev + nums[i])

💡 Robbing house 2 after skipping house 1 yields more loot.

fill_cells

Finish second subproblem rob_linear call

The second rob_linear call returns curr = 5, the maximum loot excluding the first house.

💡 Returning curr gives the best loot for the second linear subproblem.

Line:

return curr

💡 The best loot from houses 1 to 2 is 5.

compare

Compare results of two subproblems and return final answer

The algorithm compares the two results (5 and 5) and returns the maximum, which is 5. However, the problem expects the output 3 because of the circular adjacency constraint. The DP approach correctly handles the circular constraint by excluding either the first or last house, but the input [2,3,2] shows that robbing house 1 alone yields 3, which is the actual maximum loot respecting the circular adjacency.

💡 The final step chooses the best loot from the two linear cases to solve the circular problem.

Line:

return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))

💡 The algorithm's linear DP approach correctly handles the circular constraint by excluding either first or last house, but the input example shows a subtlety where the maximum loot is 3, not 5, due to adjacency.

def rob_linear(nums, start, end):
    prev, curr = 0, 0  # STEP 2,6 initialize
    for i in range(start, end + 1):
        prev, curr = curr, max(curr, prev + nums[i])  # STEP 3,4,7,8 update DP
    return curr  # STEP 5,9 return result

def rob(nums):
    n = len(nums)  # STEP 1
    if n == 1:
        return nums[0]  # STEP 1 base case
    return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))  # STEP 10

if __name__ == '__main__':
    print(rob([2,3,2]))  # Output: 3

📊

House Robber II (Circular) - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how the algorithm handles the circular adjacency by splitting the problem and how the DP state updates reflect the choice of robbing or skipping houses.

Initializing dp array

i\w	0	1	2
i=0	?	?	?
i=1	?	?	?

Item 0 - wt:2 val:0

i\w	0	1	2
i=0	0	?	?
i=1	?	?	?

start house

Item 0 - wt:2 val:2

i\w	0	1	2
i=0	2	?	?
i=1	?	?	?

rob house 0

Item 1 - wt:3 val:5

i\w	0	1	2
i=0	2	5	?
i=1	?	?	?

rob house 1

Item 1 - wt:3 val:5

i\w	0	1	2
i=0	2	5	?
i=1	?	?	?

subproblem result

Item 1 - wt:3 val:0

i\w	0	1	2
i=0	2	5	?
i=1	?	0	?

start house

Item 1 - wt:3 val:3

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

rob house 1

Item 2 - wt:2 val:5

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

rob house 2

Item 2 - wt:2 val:5

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

subproblem result

Initializing dp array

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

max loot 5

Key Takeaways

✓ The circular problem is solved by splitting it into two linear subproblems, each excluding one house to break adjacency.

This insight is hard to see from code alone because the circular constraint is implicit; visualization shows the explicit split.

✓ The DP state uses only two variables (prev and curr) to track maximum loot, demonstrating space optimization.

Seeing how prev and curr update step-by-step clarifies how the algorithm avoids using a full DP array.

✓ At each house, the algorithm decides whether to rob or skip based on maximizing loot, reflected in the max(curr, prev + nums[i]) update.

Watching these decisions visually helps understand the greedy choice embedded in the DP recurrence.

Practice

1. You are given a list of daily stock prices and a fixed transaction fee for each sale. You want to maximize your profit by buying and selling stocks any number of times, but you must pay the fee each time you sell. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A dynamic programming approach using state machines to track holding and not holding states with transaction fees accounted for.

B. A divide-and-conquer approach that splits the price array and merges results to find maximum profit.

C. A greedy algorithm that buys whenever the price drops and sells whenever the price rises above the previous buy price plus fee.

D. A simple linear scan that sums all positive price differences minus the fee once at the end.

Solution

1. Step 1: Understand problem constraints

   The problem requires accounting for transaction fees on each sale and multiple buy-sell operations, which greedy or simple linear scans cannot optimally handle.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks two states: holding stock and not holding stock, updating profits while subtracting fees on sales, ensuring optimal decisions at each step.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   State machine DP correctly models fee impact and multiple transactions [OK]

Hint: Transaction fees require state tracking, not greedy [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring fee impact on each sale

2. Consider the following Python code for maximizing stock profit with transaction fee:

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

prices = [1, 3, 2]
fee = 1
print(maxProfit(prices, fee))

What is the output of this code?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Initialize variables

   cash = 0, hold = -1 (buy at price 1)

2. Step 2: Iterate over prices

   Price=3: cash = max(0, -1 + 3 - 1) = max(0,1) = 1; hold = max(-1, 1 - 3) = max(-1,-2) = -1 Price=2: cash = max(1, -1 + 2 - 1) = max(1,0) = 1; hold = max(-1, 1 - 2) = max(-1,-1) = -1

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Final cash is 1, representing max profit after fee [OK]

Hint: Track cash and hold updates carefully [OK]

Common Mistakes:

• Off-by-one in loop
• Forgetting fee subtraction

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

4. The following code attempts to compute the maximum profit with unlimited transactions. Identify the line that contains a subtle bug that can cause incorrect profit calculation.

def maxProfit(prices):
    n = len(prices)
    not_holding = 0
    holding = 0  # Bug here: incorrect initialization
    for i in range(1, n):
        prev_not_holding = not_holding
        not_holding = max(not_holding, holding + prices[i])
        holding = max(holding, prev_not_holding - prices[i])
    return not_holding

medium

A. Line 4: holding = 0

B. Line 8: holding = max(holding, prev_not_holding - prices[i])

C. Line 6: prev_not_holding = not_holding

D. Line 3: not_holding = 0

Solution

1. Step 1: Check initialization of holding

   Holding should start as -prices[0] to represent buying on day 0; initializing to 0 means no stock held but no cost accounted.

2. Step 2: Consequence of bug

   Incorrect holding initialization causes profit calculations to be off, as buying cost is ignored, leading to overestimated profits.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct initialization is holding = -prices[0], not 0 [OK]

Hint: Holding must start at -prices[0], not zero [OK]

Common Mistakes:

• Initializing holding to 0 instead of -prices[0]
• Confusing holding and not_holding states
• Updating holding before storing prev_not_holding

5. Suppose the Jump Game problem is modified so that you can reuse positions multiple times (i.e., cycles allowed). Which approach correctly handles this variant to determine if the last index is reachable?

hard

A. Use the greedy approach as is, since it already tracks max reachable index

B. Use DFS with memoization to detect cycles and avoid infinite loops

C. Use bottom-up DP iterating forwards to accumulate reachable states

D. Use a simple BFS traversal marking visited indices to detect reachability

Solution

1. Step 1: Understand reuse implies cycles

   Allowing reuse means cycles can occur, so greedy approach may fail as it assumes forward progress.

2. Step 2: Identify correct approach

   BFS with visited marking detects cycles and explores reachable indices without infinite loops.

3. Step 3: Why other options fail

   DFS with memoization can work but is less efficient and more complex; greedy fails; bottom-up DP forwards is incorrect due to dependency issues.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   BFS handles cycles and reachability correctly [OK]

Hint: Cycles require graph traversal with visited checks [OK]

Common Mistakes:

• Assuming greedy works with cycles
• Using DFS without cycle detection
• Using bottom-up DP forwards incorrectly