LeetCode 198: House Robber

Problem Restatement

We are given an integer array nums.

Each element represents the amount of money inside one house.

A robber wants to steal as much money as possible, but there is one restriction:

Two adjacent houses cannot both be robbed.

If two adjacent houses are robbed on the same night, the alarm system activates.

We need to return the maximum amount of money that can be robbed without triggering the alarm. The official problem asks for the maximum amount of money that can be robbed without robbing adjacent houses.

Input and Output

Item	Meaning
Input	Integer array nums
Output	Maximum possible robbery amount
Restriction	Cannot rob adjacent houses
Goal	Maximize total money

Example function shape:

def rob(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 2, 3, 1]

Possible choices:

Houses robbed	Total
1 + 3	4
2 + 1	3
1 + 3 + 1	invalid

The best valid choice is:

1 + 3 = 4

Answer:

4

Example 2:

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

One good plan:

2 + 9 + 1 = 12

Answer:

12

First Thought: Try Every Combination

For every house, we have two choices:

Choice	Meaning
Rob it	Skip the next house
Skip it	Move to the next house

This creates many possible combinations.

For example:

[2, 7, 9, 3]

We might choose:

2 + 9
7 + 3
2 + 3
9
...

The number of possibilities grows exponentially.

We need a way to reuse previous results.

Key Insight

At each house, there are only two meaningful possibilities:

Option	Value
Skip current house	Best answer up to previous house
Rob current house	Current money + best answer two houses back

Suppose we are at house i.

If we rob house i, then house i - 1 cannot be robbed.

So the total becomes:

nums[i] + best(i - 2)

If we skip house i, then the total becomes:

best(i - 1)

So the recurrence is:

$$ dp[i]=\max(dp[i-1],\ dp[i-2]+nums[i]) $$

This is the core dynamic programming relation.

Algorithm

1. If there are no houses, return 0.
2. If there is one house, return its value.
3. Use dynamic programming.
4. For each house:
   • Either skip it.
   • Or rob it and add the best answer from two houses earlier.
5. Return the final maximum value.

Building the DP Table

Let:

dp[i]

mean:

Maximum money we can rob from houses 0..i

Base cases:

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

Then for every later house:

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

Correctness

For each house i, every valid robbery plan falls into one of two categories:

Category	Meaning
House i is skipped	Best value is dp[i - 1]
House i is robbed	House i - 1 must be skipped, so value is dp[i - 2] + nums[i]

No valid plan exists outside these two cases.

The recurrence chooses the better of them.

So dp[i] correctly stores the maximum robbery amount for houses 0..i.

By induction, every DP state is correct, so the final result dp[n - 1] is also correct.

Complexity

Metric	Value	Why
Time	O(n)	We process each house once
Space	O(n)	The DP array stores one value per house

Here, n is the number of houses.

Implementation

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)

        if n == 0:
            return 0

        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[-1]

Code Explanation

This handles the empty array case:

if n == 0:
    return 0

This handles a single house:

if n == 1:
    return nums[0]

We create the DP array:

dp = [0] * n

This initializes the first house result:

dp[0] = nums[0]

For two houses, we choose the larger value:

dp[1] = max(nums[0], nums[1])

Then we fill the remaining states:

for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

Finally:

return dp[-1]

returns the best possible robbery amount.

Space Optimization

Notice that:

dp[i]

depends only on:

dp[i - 1]
dp[i - 2]

So we do not need the full array.

We can keep only two variables.

Optimized Implementation

class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = 0
        prev1 = 0

        for money in nums:
            current = max(prev1, prev2 + money)

            prev2 = prev1
            prev1 = current

        return prev1

Here:

Variable	Meaning
prev1	Best answer up to previous house
prev2	Best answer up to two houses earlier

This reduces space complexity to O(1).

Testing

def run_tests():
    s = Solution()

    assert s.rob([1, 2, 3, 1]) == 4
    assert s.rob([2, 7, 9, 3, 1]) == 12
    assert s.rob([1]) == 1
    assert s.rob([2, 1, 1, 2]) == 4
    assert s.rob([0]) == 0
    assert s.rob([5, 1, 1, 5]) == 10

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
[1,2,3,1]	Main example
[2,7,9,3,1]	Multiple optimal transitions
[1]	Single house
[2,1,1,2]	Forces skipping adjacent houses
[0]	Zero-value house
[5,1,1,5]	Best choice uses first and last houses