House Robber II

MEDIUM✓ CHIP-TIMEDLC #213 — FULL STATEMENT ↗

The drill: The same street of houses, but now it loops into a circle — the first and last house are neighbors too. Maximize the non-adjacent haul under that wraparound rule.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

The same row of houses returns, but now the street bends into a circle — the first house and the last house count as neighbors too, on top of every ordinary adjacent pair.

The same no-two-adjacent rule applies under that wraparound: robbing both the first and the last house at once is exactly as forbidden as robbing any other neighboring pair.

The task is still a single maximum total haul, now respecting the circular constraint instead of the straight one.

EX 01

nums = [7]

→ 7

SINGLE HOUSE, NO WRAPAROUND CONFLICT

EX 02

nums = [5, 5]

→ 5

TWO HOUSES ARE ALWAYS ADJACENT BOTH WAYS

EX 03

nums = [3, 10, 4]

→ 10

MIDDLE HOUSE BEATS EITHER END

house count can run into the low thousands
each house's haul is a non-negative integer
first and last houses count as adjacent in addition to normal neighbors
answer is the maximum total haul under that circular rule

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The circle adds exactly one new constraint over a straight street: the first and last house can't both be robbed. What does that split the problem into?

HINT 2 THE STRUCTURE

Either the first house is off the table, or the last house is — run the ordinary street version on both cuts of the circle and see which cut wins.

HINT 3 ONE STEP FROM THE ANSWER

Solve the linear house-robber on nums[0..n-2] and again on nums[1..n-1], then take the larger of the two totals — the wraparound is handled entirely by which end you drop.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE TWO CUTSPATTERN · TWO LINEAR PASSESnums = [2, 3, 2] (circular)

CUT RESULTS

— empty —

STEP 1

The street bends into a circle — house 0 and house 2 count as neighbors too, so both can't be robbed.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/house-robber-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def line(row: List[int]) -> int:          # O(1)-space rolling DP
            prev2, prev1 = 0, 0
            for x in row:
                prev2, prev1 = prev1, max(prev1, prev2 + x)
            return prev1

        return max(line(nums[:-1]), line(nums[1:]))

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

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def line(row: List[int]) -> int:         # plain house-robber recursion, no memo
            n = len(row)

            def best(i: int) -> int:
                if i >= n:
                    return 0
                return max(best(i + 1), row[i] + best(i + 2))

            return best(0)

        return max(line(nums[:-1]), line(nums[1:]))   # drop the last house, or the first

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

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        return Math.max(line(nums, 0, n - 1), line(nums, 1, n));
    }

    // rolling O(1)-space DP over nums[from, to)
    private int line(int[] nums, int from, int to) {
        int prev2 = 0, prev1 = 0;
        for (int i = from; i < to; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

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

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        return Math.max(line(nums, 0, n - 1), line(nums, 1, n));
    }

    // plain house-robber recursion, no memo, over nums[from, to)
    private int line(int[] nums, int from, int to) {
        return best(nums, from, to);
    }

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

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

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