House Robber

📋

Problem

Imagine a professional thief planning to rob houses along a street. Each house has a certain amount of money, but robbing two adjacent houses triggers an alarm. How can the thief maximize the loot without alerting the police?

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police (i.e., you cannot rob two adjacent houses). Input: nums (list of integers). Output: integer representing maximum loot.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^4

Edge cases: Single house [5] → output 5All houses have zero money [0,0,0] → output 0Two houses with same money [10,10] → output 10

</>

IDE

def rob(nums: list[int]) -> int:public int rob(int[] nums)int rob(vector<int>& nums)function rob(nums)

def rob(nums):
    # Write your solution here
    pass

class Solution {
    public int rob(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int rob(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function rob(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 7Greedy approach picking houses with local max values without considering adjacency.✅ Implement dp recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) to consider all combinations.

Wrong: 11Robbing adjacent houses due to confusion with unbounded knapsack problem.✅ Enforce no two adjacent houses by using dp recurrence that skips adjacent indices.

Wrong: Error or non-zero on empty inputNo base case for empty input causing crash or wrong output.✅ Add base case: if nums is empty, return 0 immediately.

Wrong: 0Incorrect handling of single element input returning zero instead of nums[0].✅ Return nums[0] if length of nums is 1.

Wrong: 20Incorrect initialization of dp for two houses, summing both instead of max.✅ Initialize dp[1] = max(nums[0], nums[1]) to avoid robbing adjacent houses.

✓

Test Cases

Focus on handling base cases and small inputs correctly.

Watch out for common algorithmic traps like greedy approaches.

Optimize your solution to run efficiently on large inputs.

t1_01basic

Input{"nums":[1,2,3,1]}

Expected4

⏱ Performance - must finish in 2000ms

Rob house 1 (money = 1) and house 3 (money = 3), total = 4.

💡 Consider robbing houses such that no two adjacent houses are robbed.

💡 Use dynamic programming to decide at each house whether to rob it or skip.

💡 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) gives the max loot up to house i.

Why it failed: Incorrect output means recurrence relation is wrong; ensure dp[i] considers max of skipping or robbing current house with dp[i-2]. This is the canonical example test.

✓ Correctly implements the core recurrence relation for the House Robber problem.

t1_02basic

Input{"nums":[2,7,9,3,1]}

Expected12

⏱ Performance - must finish in 2000ms

Rob houses 1, 3, and 5 (2 + 9 + 1 = 12) for maximum loot.

💡 Try to maximize loot by choosing non-adjacent houses.

💡 Check dp values for each house to decide rob or skip.

💡 Use dp[i] = max(dp[i-1], dp[i-2] + nums[i]) to build solution.

Why it failed: Output less than 12 indicates failure to consider skipping houses properly; fix dp recurrence to include max of robbing current plus dp[i-2] or skipping current.

✓ Correctly computes maximum loot for a longer list of houses.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty list means no houses to rob, so max loot is 0.

💡 Check how your code handles empty input arrays.

💡 Base case: if no houses, return 0 immediately.

💡 Add a condition to return 0 when nums is empty.

Why it failed: Function crashes or returns non-zero on empty input; add base case to return 0 if nums is empty. This is the empty input test.

✓ Handles empty input correctly by returning 0.

t2_02edge

Input{"nums":[5]}

Expected5

⏱ Performance - must finish in 2000ms

Only one house to rob, so max loot is the value of that house.

💡 Check behavior when only one house is present.

💡 Base case: max loot is nums[0] if length is 1.

💡 Return nums[0] directly if nums length is 1.

Why it failed: Incorrect output on single element input; ensure base case returns nums[0] when length is 1. This is the single element test.

✓ Correctly returns the single house value as max loot.

t2_03edge

Input{"nums":[10,10]}

Expected10

⏱ Performance - must finish in 2000ms

Two houses with same money; can only rob one, so max loot is 10.

💡 With two houses, rob the one with maximum money.

💡 Check dp initialization for first two houses.

💡 dp[1] = max(nums[0], nums[1]) handles this case.

Why it failed: Fails to pick max of first two houses; fix dp initialization to dp[1] = max(nums[0], nums[1]). This is the exact boundary test.

✓ Correctly picks the maximum of two houses.

t3_01corner

Input{"nums":[1,2,3,1,2,3,1]}

Expected7

⏱ Performance - must finish in 2000ms

Rob houses 2, 4, and 6 (2 + 1 + 3 = 6) or 1, 3, 5, 7 (1 + 3 + 2 + 1 = 7), max is 8 by robbing houses 2, 4, 6.

💡 Beware of greedy approach that always picks the house with max immediate value.

💡 Dynamic programming considers all combinations, not just local max.

💡 Use dp recurrence to avoid greedy trap: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Why it failed: Greedy approach fails here by picking local max houses; fix by implementing dp recurrence considering previous two states. This is the greedy trap test.

✓ Correctly avoids greedy trap by using dp to maximize total loot.

t3_02corner

Input{"nums":[2,2,4,3,2,5]}

Expected11

⏱ Performance - must finish in 2000ms

Rob houses 1, 3, and 6 (2 + 4 + 5 = 11) but adjacent houses 3 and 4 conflict, so best is houses 2, 4, 6 (2 + 3 + 5 = 10).

💡 Check that you do not rob adjacent houses.

💡 Ensure dp recurrence correctly skips adjacent houses.

💡 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) enforces no adjacency.

Why it failed: Confusing 0/1 knapsack with unbounded knapsack leads to robbing adjacent houses; fix by enforcing dp recurrence that skips adjacent houses. This is the 0/1 constraint test.

✓ Correctly respects no-adjacent constraint with dp.

t3_03corner

Input{"nums":[0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All houses have zero money, so max loot is 0.

💡 Check if your code handles all zero values correctly.

💡 DP should return 0 if all nums are zero.

💡 Initialize dp with zeros and confirm max is zero.

Why it failed: Incorrect output means code does not handle zero values properly; fix initialization and max calculations to handle zeros. This is the all zero values test.

✓ Correctly returns 0 when all houses have zero money.

t4_01performance

Input{"nums":[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]}

Expected50

⏱ Performance - must finish in 2000ms

n=100, O(n) DP must complete within 2 seconds.

💡 Use O(n) time dynamic programming solution.

💡 Avoid exponential brute force recursion.

💡 Use space optimized DP to reduce memory overhead.

Why it failed: Brute force or exponential solutions will time out; implement O(n) DP with memoization or tabulation. This is the performance test.

✓ Solution runs efficiently in O(n) time and passes performance constraints.

Practice

1. Given the following code, what is the value of max_profit after the loop finishes when prices = [3, 2, 6]?

easy

A. 0

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace iteration i=1 with price=2

   min_price updated from 3 to 2, max_profit remains 0.

2. Step 2: Trace iteration i=2 with price=6

   max_profit updated to max(0, 6 - 2) = 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Max profit is 4 from buying at 2 and selling at 6 [OK]

Hint: Update min price before max profit each iteration [OK]

Common Mistakes:

• Confusing indices and off-by-one errors
• Updating max profit before min price
• Returning intermediate instead of final max profit

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 Python code implementing the optimal solution for the House Robber II problem. What is the final output when the input is [2, 3, 2]?

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

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

print(rob([2,3,2]))

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace rob_linear(nums, 0, 1)

   nums[0]=2, nums[1]=3 Iteration i=0: prev=0, curr=0 -> prev=0, curr=max(0,0+2)=2 Iteration i=1: prev=2, curr=max(2,0+3)=3 Return 3

2. Step 2: Trace rob_linear(nums, 1, 2)

   nums[1]=3, nums[2]=2 Iteration i=1: prev=0, curr=0 -> prev=0, curr=max(0,0+3)=3 Iteration i=2: prev=3, curr=max(3,0+2)=3 Return 3 Max(3,3) = 3

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both cases yield 3, final output is 3 [OK]

Hint: Trace both linear cases and pick max [OK]

Common Mistakes:

• Off-by-one in loop range
• Confusing which subarray to use
• Incorrect max calculation

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

5. What is the time complexity of the optimal dynamic programming solution for the House Robber II problem using the space-optimized approach shown below?

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

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

medium

A. O(n) with constant extra space

B. O(n²) due to nested loops

C. O(2^n) because of recursion without memoization

D. O(n) because each house is processed twice in two linear scans

Solution

1. Step 1: Identify loops in rob_linear

   rob_linear runs a single loop from start to end, which is O(n) in worst case.

2. Step 2: Count calls in rob

   rob calls rob_linear twice, each over roughly n/2 elements, so total O(n) time.

3. Step 3: Consider space usage

   The DP uses only constant extra space (variables prev and curr) during computation.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two linear scans over n elements with constant space -> O(n) time and O(1) space [OK]

Hint: Two linear scans sum to O(n) time with constant space [OK]

Common Mistakes:

• Confusing recursion with DP
• Assuming nested loops cause O(n²)
• Ignoring that calls are sequential, not nested