House Robber

MEDIUM✓ CHIP-TIMEDLC #198 — FULL STATEMENT ↗

The drill: Houses stand in a row, each holding a set haul, and robbing two adjacent houses trips the alarm. Plan the non-adjacent picks that maximize total takings.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Houses stand in a single row, each holding a fixed amount of cash. Robbing any two houses that are directly next to each other trips a connected alarm system, so adjacent picks are off the table.

The task is to choose a subset of houses, no two adjacent, whose total haul is as large as possible. Skipping houses is free — the only cost is the constraint on which pairs can't both be taken.

The answer is that single maximum total, not the list of which houses were chosen.

EX 01

nums = [5]

→ 5

SINGLE HOUSE, MINIMUM SIZE

EX 02

nums = [3, 10]

→ 10

TWO HOUSES, TAKE THE BIGGER

EX 03

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

→ 12

CLASSIC ALTERNATING PICK

house count can run into the low thousands
each house's haul is a non-negative integer
no two robbed houses may be adjacent in the row
answer is the maximum total haul, not the chosen houses

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At each house you either skip it or take it — but taking it locks out the one right before. What does the best plan up to a house actually depend on?

HINT 2 THE STRUCTURE

The best haul through house i is either the best haul that stops before i (skip this house), or this house's value plus the best haul that stopped two houses back (take it).

HINT 3 ONE STEP FROM THE ANSWER

Carry two running totals forward — best haul ending one house back and best haul ending two houses back — and at each new house take the larger of skipping or taking plus that second total.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ALTERNATING HAULPATTERN · ROLLING TWO-STATE DPnums = [2, 7, 9, 3, 1]

BEST HAUL THROUGH HOUSE

— empty —

STEP 1

No houses robbed yet — both rolling totals, one and two houses back, start at zero.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/house-robber.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0                      # best haul ending two back, one back
        for x in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 6 LN

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        def best(i: int) -> int:                # best haul from house i onward
            if i >= n:
                return 0
            skip = best(i + 1)
            take = nums[i] + best(i + 2)
            return max(skip, take)

        return best(0)

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 12 LN

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

TIME O(N)SPACE O(1)JAVA · RACE PACE · 11 LN

class Solution {
    public int rob(int[] nums) {
        return best(nums, 0);
    }

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

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED