House Robber

Medium15–20 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftLinkedIn

A thief is casing a street of houses, each holding a known amount of cash, arranged in a straight line. Every house is wired to its immediate neighbors by a shared security system — robbing two adjacent houses on the same night trips the alarm — but skipping around freely otherwise. Given the amount of cash in each house, find the maximum total that can be robbed in one night without ever robbing two neighboring houses. The key idea is that every house boils down to a single yes/no decision: rob it or leave it. Leaving it means the best possible total is whatever could already be made starting from the next house. Robbing it means banking this house's cash and jumping two houses ahead, since the very next one is now off-limits. Whichever of those two choices yields more is the best possible outcome from that point onward — and because this same two-way choice repeats at every house, it can be solved by sliding through the street once, tracking only the best totals seen at the two most recently considered houses.

Test Case 1:

Input:nums = [3, 8, 4, 9, 6]

Output:17

Explanation:Robbing houses at index 1 and 3 gives 8 + 9 = 17, and no non-adjacent combination beats it.

Test Case 2:

Input:nums = [6, 2, 5, 3, 9]

Output:20

Explanation:Robbing houses at index 0, 2, and 4 gives 6 + 5 + 9 = 20.

Test Case 3:

Input:nums = [9, 1, 1, 9]

Output:18

Explanation:Robbing the two end houses (index 0 and 3) gives 9 + 9 = 18, skipping the low-value middle pair entirely.

Constraints

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

At every house, a thief has exactly two options: skip it and move on to the next house, or rob it and skip straight past the one right next door (since robbing two adjacent houses trips the alarm). Whichever of those two choices yields more money is the best outcome from that house onward, and this decision is identical in shape at every house — so it can be expressed as a recursion on "the best haul starting from house i." Trying every house as either skipped or robbed and recursing into the corresponding next house explores every valid combination, though the same sub-problems end up solved repeatedly along different branches.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int houseRobber(int[] nums) {
        this.nums = nums;
        return solve(0);
    }

    private int solve(int i) {
        if (i >= nums.length) return 0;
        int skip = solve(i + 1);
        int take = nums[i] + solve(i + 2);
        return Math.max(skip, take);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Only the best haul from the two most recently finished houses is ever needed to decide the current one, so there is no reason to keep a full array of results. Two running variables — the best haul ending two houses back and the best haul ending one house back — are enough: at each house, either skip it (keep the one-house-back value) or rob it (take the two-house-back value plus this house's amount), and the larger of those becomes the new one-house-back value as the window slides forward. After sliding through every house, the most recent value holds the answer.

TimeO(n)

SpaceO(1)