House Robber
You are a robber planning to rob houses along a street, each with a given amount of money. Adjacent houses have connected security systems, so robbing two houses next to each other automatically alerts the police. Return the maximum amount of money you can rob without robbing two adjacent houses. At every house you face a small decision built on optimal substructure : the best total up to house i is either the best total up to house i-1 (skip this house), or the best total up to house i-2 plus this house's value (rob it). Take whichever is bigger.
Constraints
- 1 ≤ nums.length ≤ 100
- 0 ≤ numsi ≤ 400
Example
nums = [2, 7, 9, 3, 1]12Explanation Rob house 0 (2), house 2 (9), and house 4 (1): 2 + 9 + 1 = 12.
Track the best total, choosing to rob or skip each house
One cell per house on the street. Only house 0 has been decided so far — best[0] = 2.
What happens in this step
nums = [2, 7, 9, 3, 1] best[0] = max(prev1=0, prev2=0 + nums[0]=2) = 2 With only one house available, robbing it is always best. Houses 1 to 4 are still blank — they have not been decided yet.
Steps to visualize
- The row holds one cell per house: the best total you can walk away with after deciding that house.
- Each new cell only needs the two cells before it — the best total one house back and two houses back.
- At each house, the new best is max(skip this house, rob it and add to the total from two houses back).
- Shift the running totals forward and repeat for the next house.
- The final running total is the answer.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
One cell per house on the street. Only house 0 has been decided so far — best[0] = 2.
What happens in this step
nums = [2, 7, 9, 3, 1] best[0] = max(prev1=0, prev2=0 + nums[0]=2) = 2 With only one house available, robbing it is always best. Houses 1 to 4 are still blank — they have not been decided yet.
Solution
function rob(nums) {
let prev2 = 0;
let prev1 = 0;
for (const num of nums) {
const curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}- Time
- O(n)
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [1, 2, 3, 1] | 4 | example from the docstring |
nums = [2, 7, 9, 3, 1] | 12 | a second worked example |
nums = [5] | 5 | smallest valid input, a single house |
nums = [2, 1] | 2 | two houses, rob the larger one |
nums = [4, 4] | 4 | two houses of equal value, only one can be robbed |
nums = [3, 3, 3, 3, 3] | 9 | every house has the same value |
nums = [1, 2, 3, 4, 5] | 9 | strictly increasing house values |