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 this buggy code snippet for maxProfit with at most two transactions. Which line contains the subtle bug causing incorrect profit calculation?

medium

A. Line 10: Inner loop iterating forwards instead of backwards

B. Line 7: Initialization of maxDiff array

C. Line 9: Outer loop iterating from 1 to n

D. Line 6: Initialization of profit array

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates k from 1 to 2 (forwards). This causes profit[k-1] to be updated before profit[k], leading to incorrect maxDiff updates.

2. Step 2: Correct iteration order

   Iterating k backwards (from 2 down to 1) ensures profit[k-1] is from previous iteration, preserving correct state transitions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backward iteration prevents premature state overwriting [OK]

Hint: Inner loop must run backwards to avoid overwriting states [OK]

Common Mistakes:

• Iterating inner loop forwards
• Incorrect maxDiff updates

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 compute the maximum profit with transaction fee but contains a subtle bug:

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

What is the bug in this code?

medium

A. The hold update uses cash before it is updated in the same iteration.

B. The initial hold value should be zero instead of -prices[0].

C. The fee is not subtracted when selling stock, causing overestimated profit.

D. The loop should start from prices[0], not prices[1:].

Solution

1. Step 1: Identify where fee is applied

   The fee must be subtracted when selling stock, i.e., when updating cash.

2. Step 2: Locate bug in code

   cash update line adds hold + price but misses subtracting fee, leading to inflated profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing fee subtraction causes incorrect profit calculation [OK]

Hint: Fee must be subtracted exactly when selling [OK]

Common Mistakes:

• Forgetting fee on sell
• Incorrect initial hold value

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