House Robber II

medium1D Dynamic Programming45 stepsJava · Python · C++

Houses are in a circle, so the first and last are neighbours. Either the first house is skipped or the last one is. Run the linear House Robber on houses 0..n−2 and on 1..n−1, and take the better result.

▶ Watch the animated trace

Traced input: nums = [2, 3, 2, 5, 1] → 8. Original problem: neetcode.io/problems/house-robber-ii

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Two linear passes.

Key idea

You can't rob both house 0 and house n−1.
So the answer is the best of the two straight-line cases that each exclude one of them.
One house is a special case: rob it.

Common mistakes

Forgetting the single-house case (both ranges would be empty).
Excluding both ends at once loses answers.

Solution

Java

int robCircle(int[] nums) {
    if (nums.length == 1) return nums[0];
    int a = robRange(nums, 0, nums.length - 2);
    int b = robRange(nums, 1, nums.length - 1);
    return Math.max(a, b);
}

int robRange(int[] nums, int lo, int hi) {
    int prev2 = 0, prev1 = 0;
    for (int i = lo; i <= hi; i++) {
        int cur = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Python

def robCircle(nums: List[int]) -> int:
    if len(nums) == 1: return nums[0]
    a = robRange(nums, 0, len(nums) - 2)
    b = robRange(nums, 1, len(nums) - 1)
    return max(a, b)


def robRange(nums: List[int], lo: int, hi: int) -> int:
    prev2 = prev1 = 0
    for i in range(lo, hi + 1):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

C++

int robRange(vector<int>& nums, int lo, int hi) {
    int prev2 = 0, prev1 = 0;
    for (int i = lo; i <= hi; i++) {
        int cur = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int robCircle(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    int a = robRange(nums, 0, nums.size() - 2);
    int b = robRange(nums, 1, nums.size() - 1);
    return max(a, b);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Ends are neighbours Can't take both 2s.	`nums = [2, 3, 2]`	`3`
Single house No neighbours to worry about.	`nums = [7]`	`7`
Four houses 1 + 3, excluding the last house.	`nums = [1, 2, 3, 1]`	`4`