House Robber — The Skip-One DP Pattern Every FAANG Interview Tests

Problem Statement#

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. 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.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Example 1:

Input:  nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (money = 1) then rob house 3 (money = 3). Total = 4.

Example 2:

Input:  nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 1 (2), house 3 (9), house 5 (1). Total = 12.

Example 3:

Input:  nums = [2, 1, 1, 2]
Output: 4
Explanation: Rob house 1 (2) and house 4 (2). Skip houses 2 and 3.

Why This Problem Matters#

House Robber (LeetCode 198) is one of the most frequently cited dynamic programming problems in FAANG interviews. Amazon includes it in phone screens. Google uses it to test whether candidates can derive a DP recurrence from scratch rather than memorize a formula. Microsoft reaches for it in onsite loops.

Beyond its interview prevalence, House Robber is the canonical example of the skip-one DP pattern: at each position, you make a binary decision — rob now (and skip the previous house) or skip now (and keep whatever the previous best was). This exact decision structure recurs in Delete and Earn (LC 740), House Robber II (LC 213), House Robber III (LC 337, on trees), and many scheduling and selection problems.

Understanding House Robber deeply means you can immediately recognize skip-adjacency constraints in disguise, which is a genuine competitive advantage.

The Core Insight#

At each house i, you have exactly two choices:

1. Rob house i: Earn nums[i], but you cannot rob house i-1. Your total is nums[i] + dp[i-2] (best from two houses back).
2. Skip house i: Earn nothing from house i, but keep the best outcome from house i-1: dp[i-1].

Take the maximum: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Optimal substructure: the maximum amount robbed through house i depends only on the two previous subproblem answers.

Overlapping subproblems: a naive recursion recomputes the same houses repeatedly.

Base cases:

• dp[0] = nums[0] — only one house, rob it.
• dp[1] = max(nums[0], nums[1]) — with two houses, rob the richer one.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, O(2^n) — illustrative only
def rob(nums):
    def dp(i):
        if i == 0:
            return nums[0]
        if i == 1:
            return max(nums[0], nums[1])
        return max(dp(i - 1), dp(i - 2) + nums[i])
    return dp(len(nums) - 1)

// JavaScript — naive recursion
function rob(nums) {
    function dp(i) {
        if (i === 0) return nums[0];
        if (i === 1) return Math.max(nums[0], nums[1]);
        return Math.max(dp(i - 1), dp(i - 2) + nums[i]);
    }
    return dp(nums.length - 1);
}

dp(i) calls dp(i-1) and dp(i-2), both of which call dp(i-2) again, creating exponential redundancy.

Step 2 — Top-Down Memoization (O(n) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
 
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i == 0:
                return nums[0]
            if i == 1:
                return max(nums[0], nums[1])
            return max(dp(i - 1), dp(i - 2) + nums[i])
 
        return dp(n - 1)

// JavaScript — top-down memoization
var rob = function(nums) {
    const memo = new Map();
    function dp(i) {
        if (i === 0) return nums[0];
        if (i === 1) return Math.max(nums[0], nums[1]);
        if (memo.has(i)) return memo.get(i);
        const result = Math.max(dp(i - 1), dp(i - 2) + nums[i]);
        memo.set(i, result);
        return result;
    }
    return dp(nums.length - 1);
};

Step 3 — Bottom-Up Tabulation (O(n) time, O(n) space)#

# Python — bottom-up tabulation
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[n - 1]

// JavaScript — bottom-up tabulation
var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
};

Optimized Solution#

Since dp[i] depends only on dp[i-1] and dp[i-2], use two rolling variables:

# Python — space-optimized, O(n) time, O(1) space
class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2, prev1 = 0, 0
        for num in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + num)
        return prev1

// JavaScript — space-optimized, O(n) time, O(1) space
var rob = function(nums) {
    let prev2 = 0, prev1 = 0;
    for (const num of nums) {
        [prev2, prev1] = [prev1, Math.max(prev1, prev2 + num)];
    }
    return prev1;
};

The rolling variable approach uses prev2 = 0 and prev1 = 0 as initial conditions — this elegantly handles both the n=1 and n=2 base cases without explicit guards.

Visual Dry Run#

Input: nums = [2, 7, 9, 3, 1]

Answer: 12. Rob houses at indices 0 (2), 2 (9), 4 (1): total 12.

Rolling variable trace (prev2, prev1 before and after each step):

Complexity Analysis#

Common Mistakes#

1. Setting dp[1] = nums[1] instead of max(nums[0], nums[1]). With two houses, you pick the richer one. Setting dp[1] = nums[1] ignores the possibility that house 0 is more valuable.

2. Not handling n = 1 before accessing nums[1]. If n = 1 and your code sets dp[1] = max(nums[0], nums[1]), it will throw an index-out-of-bounds error. Guard with if n == 1: return nums[0].

3. Returning dp[n] instead of dp[n-1]. The array is 0-indexed; the last element is at index n-1. Returning dp[n] is out of bounds.

4. Confusing the rolling variable assignment order. In prev2, prev1 = prev1, max(prev1, prev2 + num), both right-hand sides use the old values. If you write this as two separate assignments, you must save prev1 to a temporary variable first.

5. Thinking you must always robber every other house. The optimal solution might skip two or more houses in a row if those houses have very low values. The DP handles this naturally — never assume the alternating pattern.

6. Initializing rolling variables as nums[0] and nums[1] with explicit base cases. Starting prev2, prev1 = 0, 0 and iterating over all elements is the cleanest approach. It avoids off-by-one errors and handles n=1 without a guard.

Interview Tips#

Derive the recurrence from first principles. Do not say "I know this is the House Robber recurrence." Instead, walk through the decision: "At house i, I either rob it — gaining nums[i] plus whatever I earned before house i-1 — or I skip it and keep the running best. That gives dp[i] = max(dp[i-1], dp[i-2] + nums[i])."

Show both the tabulation and the space optimization. Write the full dp array version first. Then say: "I only ever look back two positions, so I can compress this to two variables." Demonstrating the optimization signal senior-level thinking.

State the base cases carefully. Base cases are the most common source of bugs. Say aloud: "dp[0] is just nums[0] — only one house, we rob it. dp[1] is max(nums[0], nums[1]) — we pick the better of the first two."

Mention the problem family. House Robber II (circular), House Robber III (binary tree), and Delete and Earn all use this same skip-one DP pattern. Naming the pattern family impresses interviewers.

Follow-up Questions#

Q: What if the houses are arranged in a circle (first and last are adjacent)? That is House Robber II (LC 213). The solution runs the linear House Robber twice — once excluding the first house, once excluding the last — and returns the max of both results.

Q: What if the houses are arranged as a binary tree? That is House Robber III (LC 337). Use tree DP: for each node, return a pair (rob_this_node, skip_this_node) and combine children recursively.

Q: What if you must rob at least one house? The current solution already guarantees this, because we initialize prev2 = 0, prev1 = 0 and the first house always gets considered.

Q: What if you want to output which houses to rob, not just the total? Track a decision array: decision[i] = True if dp[i-2] + nums[i] > dp[i-1]. Reconstruct the path by scanning backward from n-1.

Q: What if the non-adjacency constraint is "at least 2 houses apart" instead of 1? Generalize: dp[i] = max(dp[i-1], dp[i-3] + nums[i]). Keep three rolling variables.

Q: Can you solve this with a greedy approach? No. Greedy fails on inputs like [2, 1, 1, 2] where the optimal strategy is non-obvious. DP is required.

Key Takeaways#

• The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) comes from a binary choice at each house: rob it (gaining nums[i] + best from two back) or skip it (keeping best from one back).
• The skip-one DP pattern is a fundamental building block. Recognize it whenever a problem says "cannot pick adjacent elements."
• Base cases are dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]) — or equivalently start with two zeros and iterate over all elements.
• Space optimization to O(1) uses two rolling variables prev2 and prev1, updated simultaneously each iteration.
• Always derive the recurrence from the "decision at position i" perspective, not from pattern memorization — interviewers can tell the difference.
• This pattern extends directly to House Robber II (circular), House Robber III (tree), and Delete and Earn (value deduplication before applying the same DP).