House Robber

▶

Steps

setup

Initialize prev1 and prev2

We start by setting prev1 and prev2 to 0, representing the maximum loot before considering any houses.

💡 Initializing these variables to zero sets the base case for the DP, meaning no houses robbed yet.

Line:

prev1, prev2 = 0, 0

💡 This step establishes the starting point for tracking maximum loot.

fill_cells

Consider house 0 with money 1

We look at the first house which has 1 unit of money. Calculate current max loot as max(prev1=0, prev2=0 + 1).

💡 This step shows how the algorithm decides whether to rob the first house or not.

Line:

temp = prev1
prev1 = max(prev1, prev2 + num)

💡 Robbing the first house increases loot from 0 to 1.

fill_cells

Update prev2 to prev1 for next iteration

Set prev2 to the old prev1 value (which was 0) to prepare for the next house.

💡 This update shifts the tracking window forward for the next calculation.

Line:

prev2 = temp

💡 prev2 now holds the loot value before the last house considered.

fill_cells

Consider house 1 with money 2

Calculate max loot for house 1: max(prev1=1, prev2=0 + 2) = 2.

💡 We decide whether to rob house 1 or keep previous loot.

Line:

temp = prev1
prev1 = max(prev1, prev2 + num)

💡 Robbing house 1 yields more loot than robbing house 0 alone.

fill_cells

Update prev2 to prev1 for next iteration

Set prev2 to old prev1 (which was 1) before moving to next house.

💡 This keeps track of loot two houses ago for future decisions.

Line:

prev2 = temp

💡 prev2 now holds loot after house 0, prev1 after house 1.

fill_cells

Consider house 2 with money 3

Calculate max loot for house 2: max(prev1=2, prev2=1 + 3) = 4.

💡 We decide whether to rob house 2 or keep previous max loot.

Line:

temp = prev1
prev1 = max(prev1, prev2 + num)

💡 Robbing house 2 plus house 0 yields more loot than robbing house 1 alone.

fill_cells

Update prev2 to prev1 for next iteration

Set prev2 to old prev1 (which was 2) before next house.

💡 Maintains correct loot values for comparison in next step.

Line:

prev2 = temp

💡 prev2 now holds loot after house 1, prev1 after house 2.

fill_cells

Consider house 3 with money 1

Calculate max loot for house 3: max(prev1=4, prev2=2 + 1) = 4.

💡 Decide whether robbing house 3 adds more loot or not.

Line:

temp = prev1
prev1 = max(prev1, prev2 + num)

💡 Robbing house 3 does not increase loot beyond previous max.

fill_cells

Update prev2 to prev1 for final iteration

Set prev2 to old prev1 (which was 4) after last house.

💡 Final update before returning the result.

Line:

prev2 = temp

💡 prev2 now holds loot after house 2, prev1 after house 3.

reconstruct

Return final answer

Return prev1 which holds the maximum loot possible: 4.

💡 This final value is the answer to the problem.

Line:

return prev1

💡 The algorithm successfully computed the max loot without robbing adjacent houses.

def rob(nums):
    prev1, prev2 = 0, 0  # STEP 1: Initialize
    for num in nums:
        temp = prev1  # STEP 2,4,6,8: Save prev1
        prev1 = max(prev1, prev2 + num)  # STEP 2,4,6,8: Compute max loot
        prev2 = temp  # STEP 3,5,7,9: Update prev2
    return prev1  # STEP 10: Return answer

if __name__ == '__main__':
    print(rob([1,2,3,1]))  # Expected output: 4

📊

House Robber - Watch the Algorithm Execute, Step by Step

Watching this step-by-step helps you understand how the algorithm uses previous results to make optimal choices without robbing adjacent houses.

Initializing dp array

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

Item 0 - wt:1 val:1

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

max loot after house 0

Item 0 - wt:1 val:1

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

prev1 after house 0

Item 1 - wt:2 val:2

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

max loot after house 1

Item 1 - wt:2 val:2

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

prev1 after house 1

Item 2 - wt:3 val:4

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

max loot after house 2

Item 2 - wt:3 val:4

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

prev1 after house 2

Item 3 - wt:1 val:4

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

max loot after house 3

Item 3 - wt:1 val:4

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

prev1 after house 3

Item 3 - wt:1 val:4

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

final answer

Key Takeaways

✓ The algorithm uses only two variables to track the maximum loot, making it space efficient.

This is hard to see from code alone because the logic is implicit, but the visualization shows how prev1 and prev2 evolve.

✓ At each house, the decision to rob or skip depends on comparing the loot if robbed plus loot two houses ago versus loot from the previous house.

Seeing this comparison step-by-step clarifies the DP relation and why adjacent houses cannot both be robbed.

✓ Sometimes skipping a house yields the same or better loot, illustrating that the algorithm chooses the optimal path dynamically.

The visualization highlights when the algorithm chooses to skip, which is less obvious from code alone.

Practice

1. You are given a list of daily stock prices and a maximum number of allowed transactions. You want to maximize profit by buying and selling stocks, but you cannot hold more than one stock at a time and must complete each transaction before starting another. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer splitting the price array and merging results

B. Greedy algorithm that buys whenever price is lower than the next day and sells the next day

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Dynamic programming using state machines to track buy/sell states for each transaction count

Solution

1. Step 1: Understand problem constraints and limitations of greedy

   The problem limits the number of transactions and requires maximizing profit with buy/sell states, which greedy fails to handle optimally.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks holding and not holding states per transaction count, ensuring all possibilities are considered efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy fails on multiple transactions; DP state machines handle all cases [OK]

Hint: DP with states handles transaction limits optimally [OK]

Common Mistakes:

• Assuming greedy always works for stock problems

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 and space complexity of the optimal space-optimized bottom-up DP solution for the Best Time -- Cooldown problem with input size n (number of days)?

medium

A. Time: O(n), Space: O(1)

B. Time: O(2^n), Space: O(n)

C. Time: O(n), Space: O(n)

D. Time: O(n²), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The algorithm iterates once through prices array, performing constant work per iteration -> O(n) time.

2. Step 2: Identify space complexity

   Only constant variables (hold, cool, free) are used, no arrays -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass, constant variables -> O(n) time and O(1) space [OK]

Hint: One pass with constant states means O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing recursion stack space with iterative space
• Assuming DP arrays used in bottom-up

4. The following code attempts to count the number of ways to decode a string. Which line contains a subtle bug that causes incorrect results for inputs containing '0'?

medium

A. if s[i] != '0':

B. curr += prev1 # inside two_digit check

C. if 10 <= two_digit <= 26:

D. prev2, prev1 = prev1, curr

Solution

1. Step 1: Identify two-digit addition logic

   The two-digit check should add prev2, not prev1, because it represents ways two steps back.

2. Step 2: Understand impact on '0' handling

   Adding prev1 instead of prev2 causes overcounting or invalid counts when '0' appears, e.g., '10' or '20'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct two-digit addition uses prev2, not prev1 [OK]

Hint: Two-digit addition must add prev2, not prev1 [OK]

Common Mistakes:

• Confusing prev1 and prev2 in two-digit addition

5. The following code attempts to solve the Jump Game problem optimally. Which line contains a subtle bug that causes incorrect results on edge cases like [0] or [3,2,1,0,4]?

def canJump(nums):
    maxReach = 0
    n = len(nums)
    for i in range(n):
        if i >= maxReach:
            return False
        maxReach = max(maxReach, i + nums[i])
        if maxReach >= n - 1:
            return True
    return False

medium

A. Line 4: for i in range(n):

B. Line 6: maxReach = max(maxReach, i + nums[i])

C. Line 5: if i >= maxReach:

D. Line 8: return False

Solution

1. Step 1: Analyze base case handling

   For input [0], i=0 and maxReach=0, so condition i >= maxReach is True, causing premature return False.

2. Step 2: Identify correct condition

   The condition should be i > maxReach to allow starting position when maxReach=0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing to i > maxReach fixes base case and edge failures [OK]

Hint: Check boundary conditions for i and maxReach carefully [OK]

Common Mistakes:

• Using >= instead of > in reachability check
• Ignoring single-element array base case
• Assuming greedy always works without proof