LeetCode · #198

House Robber Solution

Given an array of non-negative integers representing money in each house, return the maximum amount you can rob without robbing two adjacent houses.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #198

🏗️

Pattern

DP — 1D take/skip

You are a professional robber. Each house has a certain amount of money stashed. Adjacent houses have connected security systems — robbing two neighbors triggers an alarm. Return the maximum amount you can rob tonight.

Example

 Input: nums = [2,7,9,3,1]
Output: 12 // Rob houses 0, 2, 4 → 2 + 9 + 1 = 12 

Constraints

• 1 ≤ nums.length ≤ 100 • 0 ≤ nums[i] ≤ 400

Section Two · Approach 1

Recursion — O(2ⁿ)

For each house, decide: rob it (skip neighbor, add value) or skip it. Recursively compute both choices and take the max. This explores every possible combination.

Why it works

The recursion correctly tries all valid subsets — no two adjacent houses robbed. The maximum across all valid subsets is the answer.

Why we can do better

Problem: The recursion tree has overlapping subproblems — rob(i) is called multiple times for the same i. Total calls: O(2ⁿ). Memoization or bottom-up DP reduces this to O(n) by storing each subproblem result once.

Java — Recursive brute force

 class Solution {
public int rob(int[] nums) {
return helper(nums, nums.length - 1);
    }
private int helper(int[] nums, int i) {
if (i < 0) return 0;
return Math.max(helper(nums, i-1), // skip house i helper(nums, i-2) + nums[i]); // rob house i
}
}

Python — Recursive brute force

 class Solution:
def rob(self, nums: list[int]) -> int:
def helper(i: int) -> int:
if i < 0: return 0 return max(helper(i-1), helper(i-2) + nums[i])
return helper(len(nums)-1)

Metric	Value
Time	O(2ⁿ)
Space	O(n) call stack

Section Three · Approach 2

Two-Variable DP — O(n) time, O(1) space

At each house, the best choice is max(skip this house = prev best, rob this house = prev-prev best + this house). Since we only look back two steps, two variables suffice.

💡 Mental model: You're trick-or-treating on a street, but if you knock on a house, the next-door neighbor locks their door. At each house you face a decision: "Is the candy here plus what I collected two doors ago better than what I'd have just walking past?" You only need to remember your best haul as of the last house and the house before that — two numbers in your head. Each house updates these two running totals as you walk down the block.

Algorithm — rolling two variables

prev1 = best total including or excluding the previous house.
prev2 = best total as of two houses ago.
For each house: cur = max(prev1, prev2 + nums[i]). Then shift: prev2 = prev1; prev1 = cur.
Return prev1.

🎯 When to recognize this pattern:

"Can't pick adjacent elements, maximize/minimize sum." The signal is a take/skip decision at each index with a constraint linking adjacent choices.
Variations: LC 213 (circular), LC 740 (Delete and Earn — reduce to House Robber via frequency array), LC 746 (Min Cost Climbing Stairs).

Why two variables, not one:

The "rob this house" option needs the best excluding the previous house — that's prev2.
If you only tracked one variable, you'd lose the information about what was optimal two steps back after overwriting it.

Section Four · Trace

Visual Walkthrough

Trace for nums = [2, 7, 9, 3, 1].

House Robber — Two-Variable DP

Section Five · Implementation

Code — Java & Python

Java — Two-variable DP

 class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int cur = Math.max(prev1, prev2 + num); // skip or rob
prev2 = prev1;
            prev1 = cur;
        }
return prev1;
    }
}

Python — Two-variable DP

 class Solution:
def rob(self, nums: list[int]) -> int:
        prev2 = prev1 = 0 for num in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Naive recursion	O(2ⁿ)	O(n)	Exponential — TLE for n > 30
Memoized recursion / DP array	O(n)	O(n)	Correct but uses extra dp[] array
Two-variable DP ← optimal	O(n)	O(1)	Constant space; minimal code

Why not greedy? Greedy (always rob the richest available house) doesn't work because skipping a house may enable robbing two richer non-adjacent houses. DP considers all valid combinations by building optimal substructure.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single house	`[5]`	Rob it. prev1=5 after one iteration.
Two houses	`[1,2]`	Rob the richer one. max(1,2)=2.
All zeros	`[0,0,0]`	Max is 0. Algorithm handles naturally.
All equal	`[5,5,5,5]`	Rob alternating: 5+5=10.
Descending	`[10,5,3,1]`	Rob [10,3]=13 vs [5,1]=6. prev2+nums[i] wins early.
Large values	100 houses × 400 each	Max possible: 50×400=20,000 — fits int easily.

⚠ Common Mistake: Initializing prev1 = nums[0] and prev2 = 0 then starting the loop at i=1. This works but requires a guard for empty arrays. The cleaner pattern — start both at 0 and loop from the beginning — handles all edge cases uniformly without special-casing nums.length == 1.

← Back to DP — 1D problems

LearningTree

LC 198 · House Robber — Solution & Explanation | DSA Guide