House Robber II — LeetCode 213

What changes from Part 1?

The houses now form a circle. House 0 and house n−1 are adjacent neighbors. You still can't rob two adjacent houses.

This one extra constraint breaks the linear DP from Part 1 — you can no longer rob both ends.

Key trick: If you can't have both house 0 and house n−1, then the answer must come from one of two scenarios — either you exclude house 0 or you exclude house n−1. Run linear House Robber on each range, take the max.

Algorithm

// Two passes of linear House Robber

Pass 1: rob(nums[0 .. n−2])
// exclude last house

Pass 2: rob(nums[1 .. n−1])
// exclude first house

return max(Pass1, Pass2)

// Base case: n==1 → return nums[0]

💡 Why two passes work: In any valid solution, house 0 and house n−1 are never both robbed. So the optimal answer must lie entirely within nums[0..n−2] (skip last) or entirely within nums[1..n−1] (skip first). These two ranges together cover every possible valid selection. Run the O(n) Part 1 DP on each range and take the maximum.

How the array is split for a circle of n houses

🔵 Pass 1 — Exclude last house (n−1)

Range: nums[0 .. n−2]
House 0 is eligible · House n−1 is excluded
Finds best loot from the first n−1 houses

🔴 Pass 2 — Exclude first house (0)

Range: nums[1 .. n−1]
House 0 is excluded · House n−1 is eligible
Finds best loot from the last n−1 houses

Complexity

Time

O(n)

Two linear passes of O(n) each — still just one scan effectively.

Space

O(1)

Two variables (prev2, prev1) per pass. No dp array needed.

Sub-problems

2×

Exact same logic as Part 1, run twice on overlapping sub-arrays.

Examples & edge cases

Live Animation — House Robber II (Circular)

🔵 Pass 1: nums[0..n−2]

🔴 Pass 2: nums[1..n−1]

🏆 Compare & Return

Pass 1 active Pass 2 active Current house dp filled Excluded Answer

⏸ Waiting to start

🔵 Pass 1 dp — nums[0..n−2]

🔴 Pass 2 dp — nums[1..n−1]

🔓 Rob current

prev2 + val = —

🚶 Skip current

prev1 = —

✅ dp[i]

—

Pass 1 best

—

excl. last

Pass 2 best

—

excl. first

Current dp

—

Answer

—

Step — of —

Select an example and press Play to begin.

🏆 Max loot: —

Speed Medium

Step-by-step DP table

Step	Pass	House i	nums[i]	Rob	Skip	dp[i]	Decision

C++ implementation

house_robber_ii.cpp · LeetCode 213

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Linear House Robber on subarray [lo, hi] inclusive
    int robLinear(vector<int>& nums, int lo, int hi) {
        if (lo == hi) return nums[lo];

        int prev2 = nums[lo];
        int prev1 = max(nums[lo], nums[lo + 1]);

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

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

        // Pass 1: exclude last house  → rob range [0, n-2]
        int pass1 = robLinear(nums, 0, n - 2);

        // Pass 2: exclude first house → rob range [1, n-1]
        int pass2 = robLinear(nums, 1, n - 1);

        return max(pass1, pass2);
    }
};

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars