House Robber

Master this topic with zero to advance depth.

House Robber

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.

Visual Representation

nums = [1, 2, 3, 1]

Choice 1: Rob House 0 (1) + House 2 (3) = 4
Choice 2: Rob House 1 (2) + House 3 (1) = 3
Result: 4

DP Decision:
At each house, you have two choices:
1. Rob this house: nums[i] + maxLoot from houses (i-2)
2. Skip this house: maxLoot from houses (i-1)

Medium

Examples

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

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount = 2 + 9 + 1 = 12.

Approach 1

Level I: Brute Force (Recursive)

Intuition

For each house, we decide whether to rob it or skip it. If we rob it, we cannot rob the next house. If we skip it, we can rob the next house. We explore both paths and take the maximum.

Thought Process

rob(i) = max(nums[i] + rob(i-2), rob(i-1)).
Base cases: If index is out of bounds, return 0.

Pattern Identification

This is a Decision Based Recursion. It has many overlapping subproblems (e.g., rob(3) calls rob(1) and rob(2), and rob(2) also calls rob(1)).

⏱ O(2^n)💾 O(n) due to recursion stack

Detailed Dry Run

nums = [1, 2, 3]

Call	i	Returns	Action
1	2	max(3+f(0), f(1))	Recurse
2	0	1	Base case
3	1	max(2+f(-1), f(0))	Recurse
4	-1	0	Base case

java

public class Main {
    public static int rob(int[] nums, int i) {
        if (i < 0) return 0;
        // Decision: Rob current house + houses (i-2) OR skip current and take houses (i-1)
        return Math.max(nums[i] + rob(nums, i - 2), rob(nums, i - 1));
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max Loot: " + rob(nums, nums.length - 1));
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

We cache the result of rob(i) so that each house is only evaluated once, eliminating the exponential redundancy.

Visual

nums = [1, 2, 3, 1]
Call Tree (Memoized):
rob(3) -> max(1 + rob(1), rob(2))
rob(2) -> max(3 + rob(0), rob(1))   | memo[2] = 4
rob(1) -> max(2 + rob(-1), rob(0)) | memo[1] = 2
rob(0) -> 1 (Base Case)

⏱ O(N)💾 O(N)

Detailed Dry Run

nums = [2, 7, 9]. rob(2) = max(9+rob(0), rob(1)) = max(9+2, 7) = 11. Cached!

java

import java.util.*;

public class Main {
    static Map<Integer, Integer> memo = new HashMap<>();
    public static int rob(int[] nums, int i) {
        if (i < 0) return 0;
        if (memo.containsKey(i)) return memo.get(i);
        int result = Math.max(nums[i] + rob(nums, i - 2), rob(nums, i - 1));
        memo.put(i, result);
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println(rob(nums, nums.length - 1)); // 12
    }
}

⚠️ Common Pitfalls & Tips

Unlike the brute force, memoization ensures O(N) time. But due to the call stack, very long arrays could cause stack overflow — prefer the iterative DP for production.

Approach 3

Level III: Optimal (DP + Space Optimized)

Intuition

Thought Process

We only need the results of the two previous houses to decide for the current one. Instead of an array, we use rob1 (max loot excluding adjacent) and rob2 (max loot including adjacent).

Logic Steps

Initialize rob1 = 0 and rob2 = 0.
Iterate through each house n in nums.
temp = max(n + rob1, rob2).
rob1 = rob2.
rob2 = temp.
Return rob2.

⏱ O(n)💾 O(1)

Detailed Dry Run

nums = [1, 2, 3, 1]

i	n	rob1	rob2	Action
-	-	0	0	Init
0	1	0	1	max(1+0, 0)
1	2	1	2	max(2+0, 1)
2	3	2	4	max(3+1, 2)
3	1	4	4	max(1+2, 4)

java

public class Main {
    public static int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;
        // [rob1, rob2, n, n+1, ...]
        for (int n : nums) {
            int temp = Math.max(n + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max loot: " + rob(nums));
    }
}

⚠️ Common Pitfalls & Tips

Ensure rob1 and rob2 are updated correctly in each iteration. rob1 should always be the max loot excluding the house immediately before the current one.

← Previous QuestionCoin Change

Next Question →House Robber II

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.