A night-shift collector walks a strip of kiosks. Till i holds nums[i]. Adjacent kiosks share an alarm: take both and the circuit fires. The intern enumerated every subset that skips neighbors — a mask per kiosk, keep or drop, reject if two 1s sit next to each other. Six tills returned. A hundred-store front was still enumerating masks when the van had to leave.

House Robber asks for the maximum cash with no two adjacent houses. An array already gives nums[i] for free. Searching every legal mask uses that and still pays 2^n. At house i you only choose skip, or take plus the best through i-2.

This is an interview writeup, not a knapsack lecture. Pick-or-skip on a line is the same shape as 0/1 knapsack with weight 1 and a hard adjacency ban — a pointer, not that table.

The problem

Given an int[] nums where nums[i] is the cash in house i on a straight line, return the maximum you can take without robbing two adjacent houses. You may skip any house. Taking nothing is 0.

nums = [6, 1, 2, 9]  →  15    6 + 9  (skip the middle pair)
nums = [4, 8, 3]     →   8    the middle alone beats 4 + 3
nums = [7]           →   7
nums = [2, 1]        →   2    take the larger singleton

Note: The line is ordered. House 0 and house 2 are not neighbors; they may both be taken. This prompt is a street, not a circle. Closing the block so house 0 touches the last house is a different problem.

For each house, skip it or take it. If you take it, the next call must start at i + 2. Hitting the end is 0 more. Correct. Exponential in the length of the strip: each index forks, and overlapping suffixes are expanded again.

int robRec(int[] nums) {
    return from(nums, 0);
}

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

A bit mask 0 .. 1<<n that rejects any two consecutive set bits is the same search with worse constants. At n = 8 this is a rounding error. At a long strip you paid a subset tree for a question two rolling bests answer: skip this house, or take it plus the best through i-2? Memoizing from(i) is the same recurrence on demand.

Two integers: best through the previous house, and the one before

Walk left to right. Keep:

  • prev2 — best through houses 0..i-2 (or empty).
  • prev1 — best through houses 0..i-1.

At house i with cash x, the new best is max(prev1, prev2 + x). Then shift: yesterday’s best becomes prev2, today’s becomes prev1.

You never store n cells unless they ask. You never take two neighbors: prev2 + x skipped i-1 by construction.

nums = [6, 1, 2, 9]
         i=0 i=1 i=2 i=3

i=0  x=6   cur=max(0, 0+6)=6      prev2=0  prev1=6
i=1  x=1   cur=max(6, 0+1)=6      prev2=6  prev1=6
i=2  x=2   cur=max(6, 6+2)=8      prev2=6  prev1=8
i=3  x=9   cur=max(8, 6+9)=15     prev2=8  prev1=15

The Java is that shift:

int rob(int[] nums) {
    int prev2 = 0;
    int prev1 = 0;
    for (int x : nums) {
        int cur = Math.max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Time is O(n) — one pass, constant work per house. Space is O(1) — two rolling integers. An int[] dp with dp[i] = max(dp[i-1], dp[i-2] + nums[i]) is the same recurrence with extra cells (dp[i] = best through house i).

Note: Do not checkerboard from a fixed offset. On [4, 8, 3] the even indexes sum to 7 and the odds to 8. The recurrence already compares skip vs take at each index; a checkerboard pass is a different, weaker rule. Empty input returns 0 because both seeds stay 0.

What interviewers usually poke next

  • The dp table. Same numbers. Say you would roll it unless they want the array written out.
  • House Robber II. Houses on a circle: first and last are adjacent. Name it and stop unless they switch. Typical split: rob 0..n-2 or rob 1..n-1, then max.
  • Negative cash. The usual prompt is non-negative. A negative till is never worth taking; say you would skip it and ask if the spec allows it.
  • Reconstruct the houses. The two integers do not remember indexes. Keep a dp and walk back, or keep a prev pointer. Different ask.
  • Memo DFS. Cache from(i). Linear after the fill, linear extra. Name it, then go back to the roll.

You are done with this problem when you can walk [6, 1, 2, 9] to 15 on a whiteboard with two running bests, and you can say out loud why the subset tree is correct and why skip-vs-take-plus-i-2 is the same answer.