House Robber LeetCode 198 Deep Dive

LeetCode 198 — House Robber — gives you an array of non-negative integers representing the amount of money in each house along a street. Your goal is to maximize the total amount you can rob without triggering the alarm system, which activates if you rob two directly adjacent houses.

This constraint — you cannot rob two houses in a row — transforms a simple sum-maximization problem into a classic dynamic programming challenge. The brute-force approach of trying every subset quickly explodes in complexity, but DP reduces it to a linear scan with constant space.

House Robber is often the gateway problem for DP with an adjacency constraint. Variants of the same rob-or-skip decision appear in House Robber II (circular array), Paint House, Min Cost Climbing Stairs, and dozens of other problems. Mastering the pattern here unlocks a whole family of DP solutions.

At each house i you face exactly two choices: rob it or skip it. If you rob house i, the best you could have done at house i-2 (the last non-adjacent house) is dp[i-2], so your total becomes dp[i-2] + nums[i]. If you skip house i, you carry forward the best result from house i-1, which is dp[i-1]. You always take the larger of the two.

This gives the recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The base cases are dp[0] = nums[0] (only one house, rob it) and dp[1] = max(nums[0], nums[1]) (rob whichever of the first two is larger). For i >= 2 the recurrence applies directly, and the answer is dp[n-1].

Notice that dp[i] never looks back further than two positions. This locality is what makes space optimization possible — you never need to store the entire dp array at once, just the two most recent values.

The bottom-up approach fills a dp array of length n from left to right. Set dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]). For every index i from 2 to n-1, apply the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The final answer is dp[n-1].

This approach runs in O(n) time and O(n) space. It is easy to trace through and debug because the full dp array is available for inspection. The answer for any prefix of the array is immediately accessible at dp[k], making it useful for understanding the structure of the optimal solution.

For most interview contexts the O(n) space solution is perfectly acceptable and easier to explain. The O(1) optimization is a follow-up that demonstrates deeper understanding of which DP values are actually needed at each step.

Because dp[i] depends only on dp[i-1] and dp[i-2], you do not need to store the full dp array. Replace the array with two variables: prev1 holds dp[i-1] and prev2 holds dp[i-2]. At each step compute curr = max(prev1, prev2 + nums[i]), then shift: prev2 = prev1 and prev1 = curr. After the loop, prev1 holds the answer.

Initialize prev2 = nums[0] and prev1 = max(nums[0], nums[1]) to mirror the base cases of the array approach. The loop then runs from i = 2 to n-1. At the end, return prev1. This uses only three integer variables regardless of the input size.

The rolling-variable technique is not specific to House Robber. Any DP where dp[i] depends on only a fixed number of previous values can be compressed the same way. The number of variables you need equals the look-back distance of the recurrence.

Let nums = [2, 7, 9, 3, 1]. Walk through the dp array: dp[0] = 2 (only house 0); dp[1] = max(2, 7) = 7 (rob house 1 instead); dp[2] = max(7, 2+9) = max(7, 11) = 11 (rob houses 0 and 2); dp[3] = max(11, 7+3) = max(11, 10) = 11 (skip house 3); dp[4] = max(11, 11+1) = max(11, 12) = 12 (rob house 4).

The optimal strategy is to rob houses at indices 0, 2, and 4 for values 2 + 9 + 1 = 12. Notice that robbing the highest-value house (index 1, value 7) is suboptimal because it blocks both neighbors, and the pair (9, 1) plus 2 beats it.

With the two-variable approach: prev2 = 2, prev1 = 7. i=2: curr = max(7, 2+9) = 11; prev2=7, prev1=11. i=3: curr = max(11, 7+3) = 11; prev2=11, prev1=11. i=4: curr = max(11, 11+1) = 12; prev2=11, prev1=12. Return 12.

Python (O(n) array): def rob(nums): n = len(nums); if n == 1: return nums[0]; dp = [0]*n; dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); [dp.__setitem__(i, max(dp[i-1], dp[i-2]+nums[i])) for i in range(2, n)]; return dp[-1]. Python O(1): def rob(nums): n = len(nums); if n == 1: return nums[0]; prev2, prev1 = nums[0], max(nums[0], nums[1]); [exec("global prev2, prev1")] or None; ... use a standard for loop updating prev2 and prev1.

Java (O(1) space): public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; int prev2 = nums[0]; int prev1 = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int curr = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; }. Handle n==1 before setting prev1 to avoid ArrayIndexOutOfBoundsException on nums[1].

Both implementations must handle the n==1 edge case before accessing nums[1]. The n==2 base case is handled naturally by returning max(nums[0], nums[1]) via prev1 initialization when n >= 2, so no separate branch is needed for n==2.

House Robber II (LeetCode 213) extends this problem to a circular array where the first and last houses are adjacent. The trick is to run the same linear DP twice — once on nums[0..n-2] and once on nums[1..n-1] — and take the maximum, since you cannot rob both the first and last house.

Climbing Stairs (LeetCode 70) and Min Cost Climbing Stairs (LeetCode 746) share the same recurrence structure. Climbing Stairs asks how many ways to reach the top taking 1 or 2 steps; the recurrence dp[i] = dp[i-1] + dp[i-2] is the additive twin of House Robber's max recurrence. Paint House (LeetCode 256) is a 2D variant where each position has multiple color choices and adjacent same-color choices are forbidden.

The rob-or-skip family is one of the most important DP pattern families to internalize. Once you recognize that a problem has an adjacency constraint and a single choice per element, the recurrence dp[i] = max(dp[i-1], dp[i-2] + cost[i]) (or its sum variant) is almost always the right starting point. Variations include longer forbidden windows (k-adjacent), 2D grids, and circular arrays.