Course4all
Join us on telegram
Home/dsa/Dynamic Programming/House Robber II

House Robber II

Master this topic with zero to advance depth.

House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Visual Representation

nums = [2, 3, 2] Circle Layout: (2) -- (3) | | ( ) -- (2) Options: 1. Rob House 0: Cannot rob House 1 or House 2. Result: 2 2. Rob House 1: Cannot rob House 0 or House 2. Result: 3 Result: 3
Medium

Examples

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

You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

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

Level I: Brute Force (Recursion)

Intuition

To handle the circular constraint, we can either rob the first house (forcing us to skip the last) or skip the first house (allowing us to potentially rob the last). We run two separate recursions and compare results.

Thought Process

  1. rob(nums, start, end) is a recursive function for a linear range.
  2. In circular nums[0...n-1]:
    • Option 1: Rob from 0 to n-2.
    • Option 2: Rob from 1 to n-1.
  3. Return max(Option 1, Option 2).

Pattern Identification

Circular to Linear Reduction using Recursion.

⏱ O(2^N)💾 O(N)

Detailed Dry Run

nums = [2, 3, 2]

  1. solve(0, 1): max(2+f(-1), f(0)) = 2. Skip last house.
  2. solve(1, 2): max(2+f(0), f(1)) = 2. Skip first house. Result: 2
java
public class Main {
    private static int robLinear(int[] nums, int i, int start) {
        if (i < start) return 0;
        return Math.max(nums[i] + robLinear(nums, i - 2, start), robLinear(nums, i - 1, start));
    }

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

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2}));
    }
}
Approach 2

Level II: Top-Down DP with Helper

Intuition

We reduce the circular problem into two linear House Robber I problems (skip first house or skip last house) and apply memoization on each.

Visual

nums = [2, 3, 2] Case 1: Skip last -> rob [2, 3] -> memoized linear rob Case 2: Skip first -> rob [3, 2] -> memoized linear rob Result: max(3, 3) = 3
⏱ O(N)💾 O(N)

Detailed Dry Run

Call memoized robLinear on [2, 3] → 3. Call memoized robLinear on [3, 2] → 3. max = 3.

java
import java.util.*;

public class Main {
    private static int robLinearMemo(int[] nums, int start, int end, Map<Integer, Integer> memo) {
        if (start > end) return 0;
        if (memo.containsKey(end)) return memo.get(end);
        int res = Math.max(nums[end] + robLinearMemo(nums, start, end - 2, memo),
                           robLinearMemo(nums, start, end - 1, memo));
        memo.put(end, res);
        return res;
    }

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

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2})); // 3
    }
}

⚠️ Common Pitfalls & Tips

Since lru_cache in Python captures closure variables, use tuples as arguments for the circular-to-linear reduction to avoid cache collisions between the two sub-problems.

Approach 3

Level III: Dynamic Programming (Linear Sub-problems)

Intuition

The circular constraint means we can either rob the first house OR the last house, but never both. This simplifies the circular problem into two linear House Robber problems:

  1. Rob houses from index 0 to n-2 (exclude last).
  2. Rob houses from index 1 to n-1 (exclude first).

Thought Process

  1. If n=1, return nums[0].
  2. Calculate maxLoot1 = houseRobberLinear(nums[0...n-2]).
  3. Calculate maxLoot2 = houseRobberLinear(nums[1...n-1]).
  4. Return max(maxLoot1, maxLoot2).

Pattern Identification

This is Reducing Circular to Linear. We reuse the standard House Robber logic twice.

⏱ O(N)💾 O(1)

Detailed Dry Run

nums = [2, 3, 2]

StepSubsetMax Loot (Linear)
1[2, 3]max(2, 3) = 3
2[3, 2]max(3, 2) = 3
Finalmax(3, 3)3
java
public class Main {
    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robLinear(nums, 0, nums.length - 2), 
                        robLinear(nums, 1, nums.length - 1));
    }

    private static int robLinear(int[] nums, int start, int end) {
        int rob1 = 0, rob2 = 0;
        for (int i = start; i <= end; i++) {
            int temp = Math.max(nums[i] + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2})); // 3
    }
}

⚠️ Common Pitfalls & Tips

Don't forget the base case for n=1. If you don't handle it, slicing or indexing might fail. Also, ensure both linear calls exclude at least one house to break the circular dependency.

← Previous QuestionHouse Robber
Next Question →Jump Game