What is the brute force approach and complexity for House Robber?

Recurse from the last house: take it (look back 2) or skip it (look back 1) with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for House Robber?

Keep the last two answers and roll them forward with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for House Robber?

Look for key signals in the prompt: "take or skip each house" indicates Each house is a yes or no choice, and the answer depends on the choices made so far.; "two neighbouring houses cannot both be robbed" indicates A taken house blocks the one before it, so the look-back is 2 steps, not 1.; "the most money" indicates At each house keep the better of two options. This is a maximum that carries forward..

House Robber

Medium·LeetCode #198Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTake or skip (dp[i] = max(skip, take))

Complexity:O(2^N)→O(N)

Key Insight

Let dp[i] be the best total for houses 0..i. Then dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Skip house i keeps dp[i−1]. Take house i adds it to dp[i−2]. Each step needs only the two values before it, so two variables are enough.

Core Validity Invariant

Taking house i is legal only when we add it to dp[i − 2], because dp[i − 2] never includes house i − 1. Adding it to dp[i − 1] could put two neighbours together.

Problem

A street has a row of houses, and each house holds some money. You want to rob as much as you can, but there is one rule: if you rob two houses that sit next to each other, the alarm goes off.

Return the most money you can take without robbing two neighbouring houses.

Input

nums, a list of whole numbers. nums[i] is the money in house i.

Output

The largest total you can rob, with no two neighbouring houses both robbed.

Example 1

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

Output: 4

Rob house 0 (1) and house 2 (3). Total 4. Robbing houses 1 and 2 is not allowed, and robbing houses 1 and 3 gives only 2 + 1 = 3.

Example 2

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

Output: 12

Rob houses 0, 2 and 4: 2 + 9 + 1 = 12. No other safe set of houses gives more.

Example 3

Input: nums = [5]

Output: 5

There is only one house, so rob it.

Constraints

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

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I rob house 3, which other houses can I no longer rob?
2.
Does the best answer for houses 0 to 4 depend on the best answer for houses 0 to 3, or only on some of the earlier ones?
3.
If I know the best answer for the first few houses, what new choice do I have when I look at one more house?
4.
What should the answer be when there are no houses at all?
5.
Is the answer always the highest-money houses? Try a small row where skipping a big house is the better move.

Brute force approach

Idea

Let best(i) be the most money from houses 0..i. House i has two choices. Take it: add nums[i] and continue from i − 2, because house i − 1 is now off-limits. Skip it: continue from i − 1. Keep the larger of the two.

Thinking process

1
The answer is best(n − 1). To get it, we need the best total for the last house, and that depends on the houses before it.
2
Take [2, 7, 9, 3, 1] and look at house 4 (money 1). Taking it gives 1 + best(2) = 1 + 11 = 12. Skipping it gives best(3) = 11. The bigger one is 12.
3
To get best(2) = 11: taking house 2 gives 9 + best(0) = 9 + 2 = 11, and skipping gives best(1) = 7. So 11 wins.
4
Each house is taken or skipped, so the recursion tries every pattern. That finds the answer, but the same smaller answers get worked out again and again.
5
When there are no houses to look back at, the missing part is 0. This stops the index from going below 0.

Visual

Blue = the path from the top to the current call. Orange = a call for a house whose answer was already worked out earlier; a memo would reuse it. Purple = the houses in the answer.

Brute force repeats worknums = [2, 7, 9, 3, 1]step 1/25

tree

nums

▲i

This call

call: best(4)
house: 4 (money 1)

Already solved

none yet

New call: best(4)

Work out best(4). Take house 4 (money 1) or skip it.

Code & Implementation

brute.cpp

class Solution {
public:
    int rob(vector<int>& nums) {
        // The answer is the best total over all houses.
        return best(nums, (int)nums.size() - 1);
    }

private:
    // Best total from houses 0..i. Each house is either taken or skipped.
    int best(vector<int>& nums, int i) {
        // Take house i: it adds nums[i], and house i-1 is now off-limits, so we continue from i-2.
        int take = nums[i] + (i >= 2 ? best(nums, i - 2) : 0);
        // Skip house i: nothing is added, so we continue from i-1.
        int skip = (i >= 1 ? best(nums, i - 1) : 0);
        return max(take, skip);
    }
};

Complexity

Time O(2^N)Space O(N)

At each of the N houses the recursion takes or skips, so there are at most 2^N call paths. The no-neighbours rule makes the real count about 1.6^N (Fibonacci growth), but 2^N is the simple bound. The space is the recursion depth, which is N.

Better approach

Why brute force is slow

Each path through the take/skip choices calls best(i) again, even when the same house was already solved on another path.

What repeated work are we doing?

In the 5-house tree from the brute force, best(0) is worked out 5 times, best(1) 3 times and best(2) 2 times, always with the same answer.

What information can we reuse?

A memo of size N. Each best(i) is worked out once, and every later call returns its stored value.

New approach

Idea

The brute force asks for the same best(i) many times. Store each answer in memo[i] the first time it is worked out. The next time we need best(i), return the stored value instead of recursing again.

Thinking process

1
In the tree for [2, 7, 9, 3, 1], best(0) shows up many times. Its value is always 2, so there is no need to work it out again.
2
Keep a memo array of size n, filled with -1 for not yet. Before recursing, check memo[i]. If it is not -1, return it.
3
Check on [2, 7, 9, 3, 1]: best(1) is worked out once as max(7, 2) = 7 and stored. Every later call to best(1) returns 7 straight away.
4
The recursion itself is the same as brute force, so the answer is the same. Only the repeated work is removed.

Code & Implementation

better.cpp

class Solution {
public:
    int rob(vector<int>& nums) {
        memo.assign(nums.size(), -1);   // -1 = not computed yet (answers are never negative)
        return best(nums, (int)nums.size() - 1);
    }

private:
    vector<int> memo;   // memo[i] = best total from houses 0..i

    int best(vector<int>& nums, int i) {
        if (i < 0) return 0;                 // no houses left: nothing to earn
        if (memo[i] != -1) return memo[i];   // already solved: reuse it
        int take = nums[i] + best(nums, i - 2);
        int skip = best(nums, i - 1);
        return memo[i] = max(take, skip);
    }
};

Complexity

Time O(N)Space O(N)

There is one subproblem per house, and each one does O(1) work once its two children are known. The memo holds N values, and the recursion goes at most N deep, so the space is still O(N).

Optimized approach

Idea

Start from brute force

The brute force asks for best(i) again and again. Each answer depends only on the answers for the houses before it, so we can compute them in order, once each.

Find the repeated work

best(i) needs best(i − 1) and best(i − 2), and those are the only earlier values it ever uses. Storing all N answers is more than we need.

Define the state — what variables do I need?

prev2: dp[i − 2]: the best total for the houses up to two back. Taking house i is added to this.
prev1: dp[i − 1]: the best total for the houses up to the previous one. Skipping house i keeps this.

Define validity

Taking house i is legal only when we add it to dp[i − 2], because dp[i − 2] never includes house i − 1. Adding it to dp[i − 1] could put two neighbours together.

Define the transitions — when does each pointer move, and why is it safe?

Before the first house

prev2 = 0, prev1 = 0

With no houses, the best total is 0.

Each house x = nums[i]

cur = max(prev1, prev2 + x); prev2 = prev1; prev1 = cur

Skipping keeps prev1. Taking adds x to prev2, which is safe because prev2 has no house i − 1. Then both values move one house forward.

After the last house

return prev1

prev1 is dp[n − 1], the best total over every house.

What does the current window add to the answer?

After house i, prev1 is the best total for houses 0..i. The last value is the answer, so nothing else is added.

Code & Implementation

optimal.cpp

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0;   // best total up to two houses back (dp[i-2])
        int prev1 = 0;   // best total up to the previous house (dp[i-1]); before house 0 it is 0

        for (int x : nums) {
            // Skip this house: keep prev1. Take it: x plus prev2, because prev2 never uses the house just before.
            int cur = max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

Complexity

Time O(N)Space O(1)

One pass over the N houses, and each house does one max and a shift. Only two numbers are stored, so the extra space does not grow with N.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse from the last house: take it (look back 2) or skip it (look back 1)	O(2^N)	O(N)
Better	Store each best(i) the first time; later calls return the stored value	O(N)	O(N)
Optimal	Keep the last two answers and roll them forward	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“take or skip each house”Each house is a yes or no choice, and the answer depends on the choices made so far.
“two neighbouring houses cannot both be robbed”A taken house blocks the one before it, so the look-back is 2 steps, not 1.
“the most money”At each house keep the better of two options. This is a maximum that carries forward.

Take or skip each item+Taking one blocks its neighbour+Maximize the total→Take or skip (dp[i] = max(skip, take))

This is the anchor of the take-or-skip family. At each house the rule is take it and the house before it is out, or skip it. House Robber II changes only the two ends, which touch each other on a ring. Delete and Earn keeps this same rule but applies it to values instead of positions.

Don't make this mistake

Pattern confusion: splitting by index parity

✗ int even = 0, odd = 0; for (int i = 0; i < n; i++) (i % 2 == 0 ? even : odd) += nums[i]; return max(even, odd);

✓ int cur = max(prev1, prev2 + x); prev2 = prev1; prev1 = cur;

Houses with the same parity never touch, so each pile is a safe set. But the best set often mixes both piles. On the dry run [5, 1, 1, 9, 1, 2, 7] the even indices sum to 14 and the odd indices to 12, so the shortcut returns 14. The real answer is 21, from houses 0, 3 and 6 (5 + 9 + 7). Even [2, 1, 1, 2] fails: the shortcut gives 3, but houses 0 and 3 give 4. Only neighbours matter, not index parity.

Adding to the wrong neighbour

✗ int cur = max(prev1, prev1 + x);

✓ int cur = max(prev1, prev2 + x);

prev1 is the best up to the previous house, so it may already include house i − 1. On the dry run [5, 1, 1, 9, 1, 2, 7], house 1 gives max(5, 5 + 1) = 6, which robs houses 0 and 1 together. They are neighbours, so that is not allowed.

Greedy: rob the biggest house first

Sorting by money and grabbing the biggest house fails when a big house blocks two medium ones. On [4, 5, 4] the greedy takes the 5 in the middle and then cannot take either 4, so it gets 5. Robbing both 4s gives 8. The take-or-skip rule has to be checked house by house, in order.

Returning prev2 instead of prev1

✗ return prev2;

✓ return prev1;

With nums = [5], one loop step leaves prev1 = 5 and prev2 = 0. Returning prev2 gives 0, but the answer is 5. prev1 always holds the latest house.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — 1D Linear translate into production architectures and low-level memory mechanics.

LLD Architecture