House Robber II (LC 213)

Pattern: Dynamic Programming (circular constraint)
Difficulty: Medium
Key Concept: The circle forbids robbing both first and last; solve line House Robber twice—once excluding the last house, once excluding the first—and take the max.

Problem Statement

Same as House Robber, but houses are arranged in a circle: the first and last house are adjacent, so you cannot rob both.

Given nums, return the maximum money you can rob without robbing two adjacent houses on the ring.

Input: nums (non-negative, length ≥ 1 typically).
Output: int.

Examples:

• [2,3,2] → 3 (cannot take 2 and 2).
• [1,2,3,1] → 4 (1 + 3, skipping ends together).
• [1] → 1.

---

1. Algorithm & Pseudocode

Brute force

1. Enumerate all valid subsets of indices with no adjacent picks and not both 0 and n-1.
2. Try bitmask or recursion with extra state “did we take first?”—state space grows.

Pseudocode (naive recursion on circle):

try all subsets with no adjacent on cycle  // exponential

Optimal

1. If nums.length == 1, return nums[0].
2. Case A: Rob houses in range [0, n-2] as a line (ignore last).
3. Case B: Rob houses in range [1, n-1] as a line (ignore first).
4. Return max(caseA, caseB) using linear House Robber helper.

Pseudocode:

function linearRob(arr, start, end):
    prev2 = 0, prev1 = 0
    for i from start to end:
        cur = max(prev1, arr[i] + prev2)
        prev2 = prev1
        prev1 = cur
    return prev1

if n == 1: return nums[0]
return max(linearRob(nums, 0, n-2), linearRob(nums, 1, n-1))

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why two intervals cover all valid robberies: Any valid set on a cycle cannot include both endpoints. So either the last house is unused (all picks in 0..n-2) or the first is unused (all picks in 1..n-1). These are disjoint cases that together cover every feasible solution.

Why not run DP on the circle directly: The wrap-around couples 0 and n-1; splitting removes the cycle and reuses known linear DP.

---

3. The Dry Run

nums = [1, 2, 3, 1], n = 4.

Case A — indices 0..2: [1,2,3]
Linear rob: best = 1+3 = 4 (same as LC 198 on [1,2,3]).

Case B — indices 1..3: [2,3,1]
Linear rob: best = 3 (take middle) or 2+1=3 → 3.

Answer: max(4, 3) = 4.

Case	subarray	linear result
A	[1,2,3]	4
B	[2,3,1]	3

---

4. Java Solution

Brute Force

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return dfs(nums, 0, n - 1, false, false);
    }

    // tookFirst: robbed index 0; tookLast: robbed index n-1 — invalid if both
    private int dfs(int[] nums, int i, int last, boolean tookFirst, boolean tookLast) {
        if (i > last) {
            return 0;
        }
        int skip = dfs(nums, i + 1, last, tookFirst, tookLast);
        boolean isFirst = (i == 0);
        boolean isLast = (i == nums.length - 1);
        if (isLast && tookFirst) {
            return skip;
        }
        int take = nums[i] + dfs(nums, i + 2, last, tookFirst || isFirst, tookLast || isLast);
        return Math.max(skip, take);
    }
}

Time: Exponential. Space: O(n) stack.

Optimal

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

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

Time: O(n). Space: O(1).

---

5. The “Java vs. Others” Edge

• Helper method keeps rob readable; pass indices instead of copying subarrays (no O(n) extra slices).
• Single-house edge avoids empty range when calling linearRob.
• Same rolling variables as LC 198—interviewers often ask to implement helper once and reuse.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute DFS with flags	Exponential	O(n)	Correct but slow
Two linear DPs	O(n)	O(1)	Standard optimal