Problem statement

You plan to rob houses along a street; nums[i] is the money in house i. You cannot rob two adjacent houses (alarms connect them).

Return the maximum amount you can rob.

Example 1

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob houses 0 and 2.

Example 2

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob houses 0, 2 and 4.

Constraints

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

Hints for House Robber

1. Hint 1

   For each house: rob it (plus best excluding the previous) or skip it.

2. Hint 2

   Keep two running values: best if the last house was robbed, best if not.

How to solve House Robber

At each house there are exactly two choices: rob it — which forbids the previous one, so you add its money to the best total from two houses back — or skip it and keep the best total from the previous house. Take the larger.

Approach

1. Track two running values: the best total including up to the previous house, and the best up to the one before that.
2. For each house, compute max(skip, robTwoBack + money).
3. Shift the two values forward and continue.
4. The final value is the answer.

Why it works

The constraint is purely local — only adjacency matters — so the best plan for a prefix depends on nothing more than whether the last house was robbed. That collapses the state to two numbers. Every valid plan for the first i houses either uses house i or does not, and both branches are optimally solved by the smaller subproblems, giving optimal substructure with no overlap between the cases.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Add to the total from two houses back, not the previous one — that is the adjacency rule.
• Compute the new value before overwriting either variable, or you consume your own update.
• Houses can hold 0, so the greedy "rob every other house" heuristic fails; the max is required.
• A single house is a valid answer on its own.

Reference solution

Python

from typing import List

def rob(nums: List[int]) -> int:
    take, skip = 0, 0
    for x in nums:
        take, skip = skip + x, max(skip, take)
    return max(take, skip)

Java

public static int rob(int[] nums) {
    int prev = 0, cur = 0;
    for (int x : nums) {
        int next = Math.max(cur, prev + x);
        prev = cur;
        cur = next;
    }
    return cur;
}

C++

int rob(vector<int>& nums) {
    int prev = 0, cur = 0;
    for (int x : nums) {
        int next = max(cur, prev + x);
        prev = cur;
        cur = next;
    }
    return cur;
}

JavaScript

var rob = function(nums) {
    let take = 0, skip = 0;
    for (const x of nums) {
        const newTake = skip + x;
        skip = Math.max(skip, take);
        take = newTake;
    }
    return Math.max(take, skip);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium