102.House Robber II

MediumBlind 751-D Dynamic Programming · 4/12

Problem

Same rules as House Robber — you cannot rob two adjacent houses — except the houses are arranged in a circle: the first house nums[0] and the last house nums[n - 1] are neighbours.

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

Examples

Input:  nums = [2, 3, 2]
Output: 3
Explanation: Houses 0 and 2 are adjacent (circle), so you cannot take both 2s. Rob house 1.

Input:  nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (1) and house 2 (3).

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

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 1000

💡 Key Insight

The circle only adds one constraint: house 0 and house n - 1 can't both be robbed. So at least one of them is skipped, which means the optimal plan lives entirely inside nums[0..n-2] or inside nums[1..n-1]. Both are ordinary straight-line House Robber problems: answer = max(rob(0, n-2), rob(1, n-1)), each solved with f(i) = max(f(i - 1), nums[i] + f(i - 2)). A single house (n == 1) is the one special case.

Recursion (Brute Force)

TimeO(2ⁿ)SpaceO(n)

Intuition

Break the circle by deciding up front which end is excluded: either the last house is off-limits (houses 0..n-2) or the first one is (houses 1..n-1). Inside each range, try every rob/skip combination recursively, moving forward from the range start.

Recurrence (within a range ending at end): f(i) = max(f(i + 1), nums[i] + f(i + 2)), with f(i) = 0 for i > end.

Algorithm

If n == 1 return nums[0].
dfs(i, end): if i > end return 0; else return max(dfs(i + 1, end), nums[i] + dfs(i + 2, end)).
Return max(dfs(0, n - 2), dfs(1, n - 1)).

Visualization

Linear recursion on the range [1, 3] of nums = [1, 2, 3, 1] (index shown). f(3) is solved twice.

flowchart TD
    A["f(1)"] -->|"skip 1"| B["f(2)"]
    A -->|"rob 1: +2"| C["f(3)"]
    B -->|"skip 2"| D["f(3)"]
    B -->|"rob 2: +3"| E["f(4) = 0"]
    C -->|"skip 3"| F["f(4) = 0"]
    C -->|"rob 3: +1"| G["f(5) = 0"]
    D -->|"skip 3"| H["f(4) = 0"]
    D -->|"rob 3: +1"| I["f(5) = 0"]

Range [1, 3] gives max(2 + 1, 3) = 3; range [0, 2] gives 1 + 3 = 4; answer 4.

Code

java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // either skip the last house or skip the first house
        return Math.max(dfs(nums, 0, n - 2), dfs(nums, 1, n - 1));
    }

    // best loot from houses i..end (straight line)
    private int dfs(int[] nums, int i, int end) {
        if (i > end) {
            return 0;
        }
        int skip = dfs(nums, i + 1, end);
        int take = nums[i] + dfs(nums, i + 2, end);
        return Math.max(skip, take);
    }
}

Complexity

Time: O(2ⁿ) — two branches per house, done twice.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n)SpaceO(n)

Intuition

Inside one range, f(i) depends only on i. Memoize it — with a fresh memo per range, because the same i has different answers when the range end differs.

Algorithm

If n == 1 return nums[0].
For range [0, n-2]: new memo filled with -1, compute dfs(0).
For range [1, n-1]: new memo, compute dfs(1).
Return the larger.

Dry Run

nums = [2, 3, 2]
range [0,1]: f(1) = max(f(2)=0, 3) = 3; f(0) = max(f(1)=3, 2 + f(2)=2) = 3
range [1,2]: f(2) = 2;                   f(1) = max(f(2)=2, 3 + 0)    = 3
answer = max(3, 3) = 3

Code

java

import java.util.Arrays;

class Solution {
    private int[] memo;

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        memo = new int[n];
        Arrays.fill(memo, -1);
        int excludeLast = dfs(nums, 0, n - 2);
        memo = new int[n]; // fresh cache: answers depend on the range end
        Arrays.fill(memo, -1);
        int excludeFirst = dfs(nums, 1, n - 1);
        return Math.max(excludeLast, excludeFirst);
    }

    private int dfs(int[] nums, int i, int end) {
        if (i > end) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = Math.max(dfs(nums, i + 1, end), nums[i] + dfs(nums, i + 2, end));
        return memo[i];
    }
}

Complexity

Time: O(n) — at most n states per range, two ranges.
Space: O(n) — memo and recursion stack.

Bottom-Up Tabulation

TimeO(n)SpaceO(n)

Intuition

Run the standard House Robber table on each of the two subarrays. dp[k] = best loot using the first k houses of the subarray.

Algorithm

If n == 1 return nums[0].
Helper robRange(lo, hi): len = hi - lo + 1, dp[0] = 0, dp[1] = nums[lo], and dp[k] = max(dp[k - 1], nums[lo + k - 1] + dp[k - 2]).
Return max(robRange(0, n - 2), robRange(1, n - 1)).

Dry Run

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

range	dp[0]	dp[1]	dp[2]	dp[3]
`[0..2]` = 1, 2, 3	0	1	2	4
`[1..3]` = 2, 3, 1	0	2	3	3

Answer max(4, 3) = 4.

Code

java

class Solution {
    public 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 int robRange(int[] nums, int lo, int hi) {
        int len = hi - lo + 1;
        int[] dp = new int[len + 1]; // dp[k] = best from the first k houses of the range
        dp[1] = nums[lo];
        for (int k = 2; k <= len; k++) {
            dp[k] = Math.max(dp[k - 1], nums[lo + k - 1] + dp[k - 2]);
        }
        return dp[len];
    }
}

Complexity

Time: O(n) — two linear passes.
Space: O(n) — the dp arrays.

Space-Optimized DPOptimal

TimeO(n)SpaceO(1)

Intuition

Each range pass only needs the previous two values, so use the two-variable House Robber loop twice.

Algorithm

If n == 1 return nums[0].
robRange(lo, hi): rob1 = rob2 = 0; for i = lo..hi: newRob = max(rob2, nums[i] + rob1), shift.
Return max(robRange(0, n - 2), robRange(1, n - 1)).

Dry Run

flowchart TD
    A["nums = [2, 3, 2]<br/>circle: 0 and 2 adjacent"] --> B["exclude last<br/>rob [2, 3]"]
    A --> C["exclude first<br/>rob [3, 2]"]
    B --> D["2 → best 2<br/>3 → max(2, 3+0) = 3"]
    C --> E["3 → best 3<br/>2 → max(3, 2+0) = 3"]
    D --> F["max(3, 3) = 3"]
    E --> F

Code

java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0]; // the only house is not adjacent to anything else
        }
        // house 0 and house n-1 can't both be taken: drop one of them
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    private int robRange(int[] nums, int lo, int hi) {
        int rob1 = 0; // best up to i - 2
        int rob2 = 0; // best up to i - 1
        for (int i = lo; i <= hi; i++) {
            int newRob = Math.max(rob2, nums[i] + rob1);
            rob1 = rob2;
            rob2 = newRob;
        }
        return rob2;
    }
}

Complexity

Time: O(n) — two linear passes.
Space: O(1) — a few integers.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n)	O(n)
Bottom-Up Tabulation	O(n)	O(n)
Space-Optimized DP	O(n)	O(1)

Common Pitfalls

Forgetting n == 1: both ranges become empty and you'd return 0 instead of nums[0].
Reusing one memo across both ranges — f(i) on [0, n-2] is not the same as f(i) on [1, n-1].
Trying max(rob(nums), ...) on the whole array — the linear answer may take both ends, which is illegal here.
Thinking you need a third case "skip both ends" — it's already covered by either range.