House Robber

Difficulty: Medium Source: NeetCode

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. 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.

Example 1: Input: nums = [1,2,3,1] Output: 4

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dynamic Programming — optimal substructure and overlapping subproblems
• Greedy Thinking — why greedy alone doesn’t work here

1. Brute Force (Recursion)

Intuition

At each house, you have two choices: rob it (skip the next one) or skip it (move to the next). Recursively try both options and return the maximum. Without memoization, this explores every subset of non-adjacent houses.

Algorithm

1. Define rob(i) = max money from houses i..n-1.
2. At each house: rob(i) = max(nums[i] + rob(i+2), rob(i+1)).
3. Base cases: rob(n) = 0, rob(n-1) = nums[n-1].

Solution

def rob_brute(nums):
    n = len(nums)

    def helper(i):
        if i >= n:
            return 0
        return max(nums[i] + helper(i + 2), helper(i + 1))

    return helper(0)


print(rob_brute([1, 2, 3, 1]))    # 4
print(rob_brute([2, 7, 9, 3, 1]))  # 12
print(rob_brute([0]))              # 0
print(rob_brute([1, 2]))           # 2

Complexity

• Time: O(2^n) — binary tree of choices
• Space: O(n) — recursion stack

2. Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as the maximum money robbed from the first i houses. At house i, you either:

• Rob it: add nums[i] to the best you could do without the previous house → dp[i-2] + nums[i]
• Skip it: carry forward the best from i-1 → dp[i-1]

So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). This is exactly like Fibonacci in structure.

Since we only need the previous two values, we can use O(1) space.

Algorithm

1. Handle edge cases: if n == 1, return nums[0].
2. Initialize prev2 = nums[0], prev1 = max(nums[0], nums[1]).
3. For each house from index 2 to n-1: curr = max(prev1, prev2 + nums[i]).
4. Slide the window and return prev1.

Solution

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, n):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr

    return prev1


print(rob([1, 2, 3, 1]))     # 4  (rob houses 0 and 2: 1+3=4)
print(rob([2, 7, 9, 3, 1]))  # 12 (rob houses 0, 2, 4: 2+9+1=12)
print(rob([0]))               # 0
print(rob([1, 2]))            # 2
print(rob([2, 1, 1, 2]))      # 4  (rob houses 0 and 3)

Complexity

• Time: O(n) — single pass
• Space: O(1) — two variables

Common Pitfalls

Initializing prev1 = nums[1] instead of max(nums[0], nums[1]). The best result from the first two houses isn’t necessarily nums[1] — you might prefer to rob only nums[0] if it’s larger.

Thinking you can always rob every other house. A greedy “rob every other house” doesn’t work for inputs like [2, 1, 1, 2] — robbing indices 0 and 3 gives 4, but alternating gives only 3.

Forgetting the n=1 edge case. If there’s only one house, just rob it. The loop doesn’t run, and accessing nums[1] would be out of bounds.