House Robber

A row of houses lines a street, and nums[i] is the amount of cash stored in house i. You may take the cash from any set of houses, with one restriction: you can never take from two houses that are next to each other, because adjacent houses share an alarm.

Return the largest total amount you can collect.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Dynamic Programming · problem 153 of 169

Start simple

Try every subset of houses with no two adjacent (recursively take-or-skip each house): O(2ⁿ) time.

The key idea

Look at the problem from the end. For the first i + 1 houses, the best plan either skips house i or takes it.

• If it skips house i, what remains is exactly the same problem for houses 0..i-1.
• If it takes house i, then house i - 1 must be skipped, so the rest is the same problem for houses 0..i-2, plus nums[i].

So best(i) = max(best(i-1), best(i-2) + nums[i]). This recurrence has optimal substructure (the best plan contains a best plan for a shorter street) and overlapping subproblems (plain recursion would recompute best for the same prefix again and again, which is exponential).

Compute it from left to right instead. Each value depends only on the previous two, so two variables are enough: prev2 for the best up to two houses back and prev1 for the best up to the previous house. For each house, compute the new best and shift the pair along. Starting both at 0 handles the first two houses without special cases.

Complexity

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

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0  # best totals up to two houses back / up to the previous house
        for cash in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + cash)
        return prev1

JavaScript

var rob = function(nums) {
  let prev2 = 0; // best total up to two houses back
  let prev1 = 0; // best total up to the previous house
  for (const cash of nums) {
    const best = Math.max(prev1, prev2 + cash);
    prev2 = prev1;
    prev1 = best;
  }
  return prev1;
};

What the interviewer is checking

This is a gateway dynamic programming question: the interviewer wants to hear you define the state, derive the take-or-skip recurrence and then reduce memory to two variables.

Mistakes to avoid

• Assuming the answer is the larger of the even-index sum and the odd-index sum; skipping two houses in a row can be better.
• Index errors for one or two houses when using a dp array with i - 2.
• Returning best[n - 2] or mixing up which of the rolling variables is which after the loop.

Follow-ups to expect

• What if the houses form a circle? (Run twice: exclude first, then exclude last.)
• Return which houses to take? (Keep the dp array and backtrack.)
• What if houses form a binary tree? (Return a take/skip pair per subtree.)

In real software

Choosing non-conflicting time slots or ads where neighbours interfere, and maximum-weight independent set on a path in scheduling tools, use this same take-or-skip recurrence.

Practice next