House Robber

House Robber

What is this problem about?

The House Robber coding problem is a classic optimization task. You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. However, all houses are equipped with a security system: it will automatically contact the police if two adjacent houses are broken into on the same night. Given a list of non-negative integers representing the money in each house, you need to find the maximum amount of money you can rob tonight without alerting the police.

Why is this asked in interviews?

This is one of the most famous Dynamic Programming interview patterns. Companies like Meta, Amazon, and Google use it to see if a candidate can transition from a naive recursive approach to an optimized iterative one. It tests your ability to identify sub-problems and state transitions. If you can solve this, you demonstrate that you understand how to make a series of dependent decisions to reach a global optimum.

Algorithmic pattern used

This problem is solved using Dynamic Programming (DP). For each house $i$, you have two choices:

1. Rob house $i$: You gain the money in house $i$ plus the maximum money you could get up to house $i-2$ (to avoid adjacency).
2. Skip house $i$: You keep the maximum money you could get up to house $i-1$. The recurrence relation is: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). You can optimize this to $O(1)$ space by only keeping track of the last two values instead of a full DP array.

Example explanation

Houses: [1, 2, 3, 1]

1. House 0 (val 1): Max loot = 1.
2. House 1 (val 2): Max(1, 2) = 2.
3. House 2 (val 3): Max(House 1 loot, House 0 loot + 3) = Max(2, 1 + 3) = 4.
4. House 3 (val 1): Max(House 2 loot, House 1 loot + 1) = Max(4, 2 + 1) = 4. Total Max: 4 (Rob houses at index 0 and 2).

Common mistakes candidates make

• Greedy Approach: Trying to pick the largest house first or simply alternating between all even and all odd houses. This fails for cases like [2, 1, 1, 2].
• Exponential Recursion: Implementing a solution without memoization, leading to $O(2^n)$ complexity.
• Base Cases: Not correctly handling arrays with 0, 1, or 2 houses.

Interview preparation tip

Always look for the "Decision" in DP problems. For each item, the question is usually "Should I include this or not?" Once you define the consequences of that choice, the DP state follows naturally.