House Robber II — InterviewPrepKit

Solving tips

The circle only means houses 0 and n-1 can't both be robbed, so run the linear House Robber twice and take the max.
Solve max(rob_line(nums[:-1]), rob_line(nums[1:])) - once excluding the last house, once excluding the first.
Special-case n==1 up front, since slicing off an end would empty the array and lose the only value.
Don't grab both ends: [5,1,1,5] gives 6, not 10; target O(n) time, O(1) space per pass with two rolling scalars.

Problem

You’re given an integer array nums where nums[i] is the amount of money stashed in house i. The houses are arranged in a circle, so the first and last houses are neighbors. A silent alarm trips if you rob two adjacent houses on the same night. Return the maximum total you can rob without ever hitting two adjacent houses.

Because the houses form a circle, robbing house 0 forbids robbing house n-1, and vice versa.

Examples

nums = [2,3,2] → 3 — you cannot rob houses 0 and 2 (they are adjacent on the circle), so the best single choice is house 1 for 3.
nums = [1,2,3,1] → 4 — rob house 0 (1) and house 2 (3); houses 0 and 3 are not both taken, so no wrap conflict.
nums = [1,2,3] → 3 — take just house 2.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Think about it first

Hint 1

Forget the circle for a moment. If the houses were in a straight line, what's the max you can rob? That's the classic House Robber recurrence: at each house you either skip it (keep the best so far) or take it (add it to the best from two houses back).

Hint 2

The only thing the circle adds is: house 0 and house n-1 can't both be robbed. So split into two independent line problems — one that excludes the last house, one that excludes the first — and take the better.

Hint 3

Answer = max(rob_line(nums[0 .. n-2]), rob_line(nums[1 .. n-1])), where rob_line is the linear House Robber. Handle n == 1 as a special case (a single house has no neighbor to conflict with).

TL;DR

Run the linear House Robber twice — once without the last house, once without the first — and take the max. O(n) time, O(1) space.

Approach 1 — Brute-force recursion

The choice at each house is binary: rob it or skip it. Recurse over both, honoring the “no two adjacent” rule, and the circle rule that houses 0 and n-1 cannot both be robbed. The cleanest framing is to decide up front whether house 0 is allowed, which fixes whether house n-1 is allowed.

Recurrence (linear, over a slice): rob(i) = max(rob(i-1), nums[i] + rob(i-2)) — skip house i, or take it and jump two back. Base: rob(<0) = 0.

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

        def rob_line(lo: int, hi: int) -> int:
            # max robbery over nums[lo..hi] inclusive, no two adjacent
            def rec(i: int) -> int:
                if i < lo:
                    return 0
                return max(rec(i - 1), nums[i] + rec(i - 2))
            return rec(hi)

        return max(rob_line(0, n - 2), rob_line(1, n - 1))

Complexity: each rec(i) fans out into two calls → O(2ⁿ) time. At n = 100 this is hopeless.

Approach 2 — Memoized top-down

The insight: rec(i) depends only on i, so there are just n distinct subproblems. Cache them.

from functools import lru_cache

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

        def rob_line(lo: int, hi: int) -> int:
            @lru_cache(maxsize=None)
            def rec(i: int) -> int:
                if i < lo:
                    return 0
                return max(rec(i - 1), nums[i] + rec(i - 2))
            return rec(hi)

        return max(rob_line(0, n - 2), rob_line(1, n - 1))

Complexity: O(n) time, O(n) space (cache + recursion stack) per line, run twice.

Approach 3 — Tabulated bottom-up

The insight: fill dp left to right, where dp[i] is the best robbery over the slice up to house i.

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

        def rob_line(sub: list[int]) -> int:
            m = len(sub)
            if m == 0:
                return 0
            dp = [0] * m
            dp[0] = sub[0]
            for i in range(1, m):
                take = sub[i] + (dp[i - 2] if i >= 2 else 0)
                dp[i] = max(dp[i - 1], take)
            return dp[-1]

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

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (two rolling variables)

The insight: dp[i] only ever reads dp[i-1] and dp[i-2], so keep two scalars instead of the whole array.

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

        def rob_line(sub: list[int]) -> int:
            prev, cur = 0, 0  # cur = best incl. house i-1, prev = best incl. i-2
            for x in sub:
                prev, cur = cur, max(cur, prev + x)
            return cur

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

Walkthrough (nums = [1,2,3,1]):

Exclude last → line [1,2,3]: (prev,cur) goes (0,0)→(0,1)→(1,2)→(2,4). Best 4.
Exclude first → line [2,3,1]: (0,0)→(0,2)→(2,3)→(3,3). Best 3.
Answer max(4, 3) = 4. ✓

Complexity: O(n) time, O(1) space.

Common pitfalls

Forgetting the n == 1 special case: with one house there is no wrapping neighbor, and slicing off “the last house” would leave an empty list and lose the only value.
Robbing both ends: [5, 1, 1, 5] tempts you into 5 + 5 = 10, but houses 0 and 3 are adjacent on the circle — the real answer is 5 + 1 = 6.
Trying to patch the linear DP with a single “did I take house 0?” flag threaded through — the two-pass split is far cleaner and provably correct.

Pattern takeaway

When a linear DP gets a wrap-around or global mutual-exclusion twist, don’t invent a new recurrence — fix the conflicting element two ways and solve the simpler linear problem once per case, then combine. Reducing a circular constraint to two runs of the linear solution is a reusable move.