LeetCode 198 - House Robber

LeetCode Problem 198

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem describes a row of houses, where each house contains some amount of money. You are acting as a robber who wants to maximize the total amount stolen, but there is one important restriction, you cannot rob two adjacent houses. If you rob neighboring houses on the same night, the alarm system will notify the police.

The input is an integer array nums, where nums[i] represents the amount of money available in the i-th house. Your task is to determine the maximum amount of money that can be stolen without robbing two consecutive houses.

Another way to think about the problem is that for every house, you have exactly two choices:

1. Rob the current house, which means you must skip the previous house.
2. Skip the current house, which means your total remains whatever was best so far.

The output is a single integer representing the largest total amount of money you can rob while respecting the adjacency rule.

The constraints are relatively small:

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

Since the array length is at most 100, even slower approaches could theoretically work. However, the problem is designed to teach an important dynamic programming pattern, where a local decision depends on previous optimal decisions. A brute-force solution is possible, but inefficient due to repeated calculations.

There are several important edge cases worth identifying before implementation.

A single house is the simplest case. If nums = [5], there are no adjacency conflicts, so the answer is simply 5.

Arrays where all houses contain 0 must still work correctly. For example, [0,0,0] should return 0.

Cases where robbing many small houses beats one large house can trip up greedy thinking. For example, [2,1,1,2] should return 4, because robbing both end houses gives a better result than greedily taking a larger nearby value.

The problem guarantees at least one house exists, so we never need to handle an empty array.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to try every possible combination of houses while enforcing the rule that adjacent houses cannot both be robbed.

For every house, we make two recursive choices:

• Rob the current house and skip the next one.
• Skip the current house and move to the next.

This creates a decision tree where each position branches into two possibilities. Eventually, we compute the maximum money achievable.

For example, with [2,7,9,3,1], the recursion repeatedly explores overlapping subproblems. The best answer for later portions of the array gets recomputed many times. This repeated work makes the solution inefficient.

The brute-force recurrence looks like this:

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

The issue is that the same states are recalculated repeatedly, causing exponential growth in runtime.

Optimal Dynamic Programming Approach

The key observation is that the problem exhibits optimal substructure.

At each house i, the best answer depends only on two previous situations:

• The maximum amount if we skip house i
• The maximum amount if we rob house i

Suppose we are at house i.

If we rob it, we cannot rob i - 1, so we add nums[i] to the best answer up to i - 2.

If we skip it, we simply carry forward the best answer up to i - 1.

This gives the recurrence:

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

Since each state depends only on the previous two states, we do not need an entire DP array. We can optimize space to constant memory by tracking only two variables.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explores every rob or skip combination recursively
Optimal	O(n)	O(1)	Uses dynamic programming with only two variables

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Initialize two variables to represent previous results.

We keep track of:

• prev_two, the maximum money obtainable up to house i - 2
• prev_one, the maximum money obtainable up to house i - 1

Initially, both are 0 because before processing any houses, we have robbed nothing. 2. Iterate through each house in nums.

For every house value money, we decide whether robbing or skipping produces a larger total. 3. Compute the new best value.

There are two possibilities:

• Skip the current house, which gives prev_one
• Rob the current house, which gives prev_two + money

We take:

$$current = \max(prev_one, prev_two + money)$$ 4. Shift the state forward.

After processing the current house:

• prev_two becomes the old prev_one
• prev_one becomes current

This prepares us for the next iteration. 5. Return the final result.

After processing all houses, prev_one contains the maximum possible amount.

Why it works

The algorithm maintains an important invariant:

prev_one always stores the maximum money obtainable from all houses processed so far, while prev_two stores the result excluding the immediately previous house.

At each step, the algorithm compares the only two valid possibilities, robbing or skipping the current house. Since every decision is based on already optimal previous results, the final answer is globally optimal. This follows the principle of dynamic programming, where optimal solutions are built from optimal subproblems.

Python Solution

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev_two = 0
        prev_one = 0

        for money in nums:
            current = max(prev_one, prev_two + money)
            prev_two = prev_one
            prev_one = current

        return prev_one

The implementation uses two variables instead of a full dynamic programming array.

prev_two stores the best result from two houses ago, while prev_one stores the best result from the previous house. For each house, we compute current as the better of two choices: skip the house or rob it.

After calculating current, we shift the variables forward so they represent the correct state for the next iteration.

This implementation directly follows the recurrence relation while reducing space complexity from O(n) to O(1).

Go Solution

func rob(nums []int) int {
	prevTwo := 0
	prevOne := 0

	for _, money := range nums {
		current := max(prevOne, prevTwo+money)
		prevTwo = prevOne
		prevOne = current
	}

	return prevOne
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation mirrors the Python logic closely. Since Go does not provide a built-in max function for integers, we define a helper function.

The solution uses integer variables rather than additional slices, keeping space usage constant. Go slices naturally handle the input array efficiently, and since the constraints are small, integer overflow is not a concern because the maximum possible sum is well within Go's integer range.

Worked Examples

Example 1

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

We track the values of prev_two and prev_one at each step.

House Value	Rob Option (prev_two + money)	Skip Option (prev_one)	Current Best	prev_two	prev_one
Start	-	-	-	0	0
1	1	0	1	0	1
2	2	1	2	1	2
3	4	2	4	2	4
1	3	4	4	4	4

Final answer: 4

The optimal choice is robbing houses with values 1 and 3.

Example 2

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

House Value	Rob Option (prev_two + money)	Skip Option (prev_one)	Current Best	prev_two	prev_one
Start	-	-	-	0	0
2	2	0	2	0	2
7	7	2	7	2	7
9	11	7	11	7	11
3	10	11	11	11	11
1	12	11	12	11	12

Final answer: 12

The optimal houses are 2, 9, and 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each house is processed exactly once
Space	O(1)	Only a fixed number of variables are used

The runtime is linear because the algorithm scans the input array exactly once. Each iteration performs only constant-time operations.

The space complexity is constant because regardless of input size, the algorithm stores only three integer variables: prev_two, prev_one, and current.

Test Cases

solution = Solution()

assert solution.rob([1, 2, 3, 1]) == 4  # Example 1
assert solution.rob([2, 7, 9, 3, 1]) == 12  # Example 2
assert solution.rob([5]) == 5  # Single house
assert solution.rob([0]) == 0  # Single zero-valued house
assert solution.rob([1, 2]) == 2  # Choose larger of two adjacent houses
assert solution.rob([2, 1, 1, 2]) == 4  # Rob non-adjacent ends
assert solution.rob([2, 7, 9]) == 11  # Rob first and third
assert solution.rob([10, 1, 1, 10]) == 20  # Large values at ends
assert solution.rob([0, 0, 0, 0]) == 0  # All houses empty
assert solution.rob([4, 1, 2, 7, 5, 3, 1]) == 14  # Mixed pattern
assert solution.rob([100, 1, 1, 100]) == 200  # Optimal non-adjacent selection
assert solution.rob([400] * 100) == 20000  # Maximum constraint size

Test	Why
[1,2,3,1]	Validates the first provided example
[2,7,9,3,1]	Validates the second provided example
[5]	Tests single-element input
[0]	Tests minimum money case
[1,2]	Ensures adjacent constraint is respected
[2,1,1,2]	Prevents greedy mistakes
[2,7,9]	Verifies skipping adjacent houses
[10,1,1,10]	Tests large values separated by small values
[0,0,0,0]	Ensures zero totals are handled
[4,1,2,7,5,3,1]	Tests a realistic mixed pattern
[100,1,1,100]	Validates choosing distant large houses
[400] * 100	Stresses maximum constraints

Edge Cases

Single House

When the input contains only one house, there is no adjacency conflict. A naive implementation might incorrectly assume at least two houses exist and attempt invalid indexing. This implementation avoids the issue entirely because the loop simply processes one value and returns it.

Two Adjacent Houses

For inputs such as [1,2], only one house can be robbed. A flawed greedy approach might accidentally combine both values. The dynamic programming recurrence correctly evaluates the two legal options and selects the larger value.

Multiple Zero Values

Arrays like [0,0,0,0] can expose bugs where logic assumes some positive gain exists. The implementation handles this naturally because each step compares valid totals, and the maximum remains 0.

Greedy Trap Cases

Cases such as [2,1,1,2] are important because greedy strategies often fail. Choosing the locally largest house does not always produce the best overall result. The dynamic programming approach succeeds because it evaluates the cumulative optimal result at every step rather than making short-sighted decisions.