House Robber II

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonAdobeMicrosoft

This is the same street of houses as before, except now the street bends into a circle: the very first house and the very last house sit right next to each other, so robbing both on the same night still trips the alarm. Given each house's cash, find the maximum total that can be robbed without ever robbing two adjacent houses — including that one wraparound pair. The circular constraint only ever rules out one thing: robbing both the first and last house together. So instead of solving the whole circle at once, break it into two ordinary straight-line streets — one that stops just before the last house, and one that starts just after the first house — and solve each with the regular House Robber approach. Since any valid circular plan must leave out the first house, the last house, or both, one of these two straight-line streets is guaranteed to already contain the best possible plan, and the larger of the two results is the final answer.

Test Case 1:

Input:nums = [5, 4, 7, 3]

Output:12

Explanation:Excluding house 3 breaks the wraparound adjacency with house 0, and the best combination in the remaining range is house 0 and house 2: 5 + 7 = 12.

Test Case 2:

Input:nums = [8, 1, 1, 8]

Output:9

Explanation:Excluding house 3, the best combination is house 0 and house 2: 8 + 1 = 9.

Test Case 3:

Input:nums = [6, 3, 9, 5, 2, 7]

Output:17

Explanation:Excluding house 5, the best combination is house 0, house 2, and house 4: 6 + 9 + 2 = 17.

Constraints

◆1 ≤ nums.length ≤ 100
◆0 ≤ nums[i] ≤ 400
◆The houses are arranged in a circle: the first and last houses are adjacent to each other.

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Because the houses form a circle, the first and last houses are adjacent, so they can never both be robbed. That means a valid plan either robs from a range that stops before the last house, or one that starts after the first house — one of those two linear ranges is guaranteed to contain the true best plan (a lone house is handled separately since it has no meaningful "circle" to break). Each of those two ranges is just the ordinary House Robber recursion, generalized to take a starting index and an ending index instead of always running to the end of the array: at every house in range, either skip it and move to the next, or rob it and jump two ahead. The larger result from the two ranges is the overall answer.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int houseRobberII(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(solve(0, n - 2), solve(1, n - 1));
    }

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

Optimal — Bottom-Up 1D DP

Optimal

The same two-range idea applies to the constant-space sliding version of House Robber: run the prev2/prev1 sweep once over the range that excludes the last house, run it again over the range that excludes the first house, and return whichever total is larger. Neither sweep ever considers robbing both the first and last house together, so the circular constraint is respected automatically, and each sweep itself still only needs O(1) extra space.

TimeO(n)

SpaceO(1)