Problem statement

Same as House Robber, but the houses form a circle — the first and last houses are adjacent.

Return the maximum amount you can rob without alerting the police.

Example 1

Input: nums = [2,3,2]
Output: 3
Explanation: Houses 0 and 2 are adjacent in the circle.

Example 2

Input: nums = [1,2,3,1]
Output: 4

Example 3

Input: nums = [1,2,3]
Output: 3

Constraints

• 1 <= nums.length <= 30
• 0 <= nums[i] <= 400

Hints for House Robber II

1. Hint 1

   You can never rob BOTH the first and last house.

2. Hint 2

   Solve the linear problem twice: once without the first house, once without the last.

How to solve House Robber II

The circle adds exactly one new constraint: the first and last houses are now adjacent, so they cannot both be robbed. That splits the problem into two linear instances — one that excludes the last house, one that excludes the first — and the answer is the better of the two.

Approach

1. Handle a single house directly: the answer is its money.
2. Otherwise run the plain linear House Robber on nums[0 .. n-2].
3. Run it again on nums[1 .. n-1].
4. Return the maximum of the two results.

Why it works

Any valid circular plan must leave out the first house or the last one — it cannot include both. The first case is contained in the range 1 .. n-1 and the second in 0 .. n-2, and both ranges are plain lines where the original algorithm applies. The two cases together cover every possibility, so the maximum is exact. Overlap between them is harmless: a plan counted twice is still valid.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• A single house must be special-cased — otherwise both ranges are empty and the answer comes out as 0.
• The two ranges must each omit exactly one endpoint; omitting neither reintroduces the forbidden pair.
• It is not necessary to force either endpoint to be robbed — merely allowing at most one of them is enough.
• Two houses works with the same split, each range holding one house.

Reference solution

Python

from typing import List

def rob(nums: List[int]) -> int:
    def rob_line(row):
        take, skip = 0, 0
        for x in row:
            take, skip = skip + x, max(skip, take)
        return max(take, skip)

    if len(nums) == 1:
        return nums[0]
    return max(rob_line(nums[1:]), rob_line(nums[:-1]))

Java

public static int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

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

C++

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

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

JavaScript

var rob = function(nums) {
    function robLine(row) {
        let take = 0, skip = 0;
        for (const x of row) {
            const newTake = skip + x;
            skip = Math.max(skip, take);
            take = newTake;
        }
        return Math.max(take, skip);
    }
    if (nums.length === 1) return nums[0];
    return Math.max(robLine(nums.slice(1)), robLine(nums.slice(0, -1)));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium