Skip to main content
CodePeetCodePeet
CodePeet 250

House Robber II

MEDIUMProblemSolveExternal Links

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed inside. However, there is a twist: all the houses on this street are arranged in a circle. This means the first house and the last house are neighbors of each other.

Adjacent houses are connected by a security system. If two adjacent houses are broken into on the same night, the alarm will trigger and the police will be alerted.

Given an integer array nums where nums[i] represents the amount of money in the i-th house, determine the maximum amount of money you can rob tonight without alerting the police.

The circular arrangement means you must be extra careful: if you choose to rob the first house, you cannot rob the last house, and vice versa.

Examples

Example 1

Input: nums = [2, 3, 2]

Output: 3

Explanation: The houses form a circle: house 0 (money=2), house 1 (money=3), and house 2 (money=2). House 0 and house 2 are neighbors because of the circular arrangement. If we rob house 0 and house 2, the alarm triggers. The best strategy is to rob only house 1, collecting 3.

Example 2

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

Output: 4

Explanation: The four houses form a circle. We can rob house 0 (money=1) and house 2 (money=3) since they are not adjacent. Total = 1 + 3 = 4. Alternatively, robbing house 1 (money=2) and house 3 (money=1) gives only 3. So the maximum is 4.

Example 3

Input: nums = [1, 2, 3]

Output: 3

Explanation: We cannot rob house 0 and house 2 together (they are adjacent in the circle). The best option is to rob house 2 alone for a total of 3.

Constraints

  • 1 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 1000

Editorial

Brute Force

Intuition

The most natural way to approach this problem is to think about every possible combination of houses we could rob. For each house, we have two choices: rob it or skip it. But we also need to respect two rules — we cannot rob two adjacent houses, and because the houses are in a circle, the first and last houses are also considered adjacent.

Imagine you are standing in front of the first house. You can either rob it or skip it. If you rob it, the last house becomes off-limits. If you skip it, the last house is still available. This gives us two separate scenarios to consider:

  1. Include house 0: Solve the problem for houses 0 through n-2 (the last house is excluded).
  2. Exclude house 0: Solve the problem for houses 1 through n-1 (the first house is excluded).

For each scenario, we recursively try every valid combination — for each house, we either rob it (and skip the next house) or skip it (and move to the next house). We take the maximum amount from all valid combinations across both scenarios.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 1]:

Since the houses form a circle, we break this into two linear problems:

  • Scenario A: Consider houses [1, 2, 3] (indices 0 to 2, exclude last house)
  • Scenario B: Consider houses [2, 3, 1] (indices 1 to 3, exclude first house)

Scenario A: houses = [1, 2, 3]

Step 1: Start at house 0 (value=1). Choice: rob or skip.

Step 2: If we rob house 0 (gain 1), we skip house 1 and move to house 2.

  • At house 2 (value=3): rob it → total = 1 + 3 = 4.
  • At house 2 (value=3): skip it → total = 1.

Step 3: If we skip house 0, move to house 1.

  • At house 1 (value=2): rob it, skip house 2 → total = 2.
  • At house 1 (value=2): skip it, move to house 2.
    • At house 2 (value=3): rob it → total = 3.
    • At house 2 (value=3): skip it → total = 0.

Step 4: Maximum from Scenario A = max(4, 1, 2, 3, 0) = 4.

Scenario B: houses = [2, 3, 1]

Step 5: Following similar recursive exploration:

  • Rob house 1 (2) + rob house 3 (1) = 3.
  • Rob only house 2 (3) = 3.
  • Maximum from Scenario B = 3.

Step 6: Final answer = max(4, 3) = 4.

Brute Force Recursion — Exploring All Valid Subsets — Watch how the recursive approach branches at each house: rob it (skip the next) or skip it (move to the next). We trace Scenario A with houses [1, 2, 3].

Algorithm

  1. Handle edge case: if there is only one house, return its value.
  2. Split the circular problem into two linear problems:
    • Scenario A: Consider houses from index 0 to n-2 (exclude the last house).
    • Scenario B: Consider houses from index 1 to n-1 (exclude the first house).
  3. For each scenario, use recursion to try all valid combinations:
    • At each house, either rob it (add its value, skip the next house) or skip it (move to the next house).
    • Return the maximum value among all valid choices.
  4. Return the maximum of the two scenarios.

Code

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

private:
    int robLinear(vector<int>& nums, int start, int end) {
        if (start > end) return 0;
        // Rob current house + skip next, or skip current house
        int robCurrent = nums[start] + robLinear(nums, start + 2, end);
        int skipCurrent = robLinear(nums, start + 1, end);
        return max(robCurrent, skipCurrent);
    }
};
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def rob_linear(start: int, end: int) -> int:
            if start > end:
                return 0
            rob_current = nums[start] + rob_linear(start + 2, end)
            skip_current = rob_linear(start + 1, end)
            return max(rob_current, skip_current)

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

    private int robLinear(int[] nums, int start, int end) {
        if (start > end) return 0;
        int robCurrent = nums[start] + robLinear(nums, start + 2, end);
        int skipCurrent = robLinear(nums, start + 1, end);
        return Math.max(robCurrent, skipCurrent);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each house, we make two recursive calls (rob or skip). This creates a binary recursion tree of depth n, resulting in up to 2^n calls. Many subproblems overlap but are recomputed since we do not use memoization.

Space Complexity: O(n)

The recursion stack can go up to n levels deep in the worst case (when we skip every house one by one). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force recursion has O(2^n) time complexity. With n up to 100, this means up to 2^100 ≈ 10^30 operations — astronomically beyond any reasonable time limit.

The root cause is overlapping subproblems. When deciding whether to rob house i, the recursive calls rob(i+1) and rob(i+2) share many common sub-calls deeper in the tree. The same subproblem rob(k) is computed over and over again.

The key insight: since each subproblem's answer depends only on its start index (and the fixed end), we can store the result of each subproblem and reuse it. This transforms our approach from exponential to linear — the essence of dynamic programming.

Better Approach - Dynamic Programming with Array

Intuition

Instead of recomputing the same subproblems, we can use a DP array to build the solution bottom-up. The idea remains the same: break the circle into two linear problems, but now we solve each linear problem efficiently.

For a linear arrangement of houses, define dp[i] as the maximum money we can rob from the first i houses. At each house, we have two choices:

  • Rob house i: We get nums[i] plus the best we could do from houses up to i-2 (since we must skip the adjacent house). This gives dp[i-2] + nums[i].
  • Skip house i: We keep the best we had from houses up to i-1. This gives dp[i-1].

So the recurrence is: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

We run this DP twice — once excluding the last house, once excluding the first — and take the maximum.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 1]:

Scenario A: houses = [1, 2, 3] (indices 0 to 2)

Step 1: Initialize dp array. dp[0] = 1 (only one house available, rob it).

Step 2: dp[1] = max(dp[0], nums[1]) = max(1, 2) = 2. Between house 0 and house 1, robbing house 1 gives more.

Step 3: dp[2] = max(dp[1], dp[0] + nums[2]) = max(2, 1 + 3) = max(2, 4) = 4. Robbing houses 0 and 2 gives 4, which beats just robbing house 1.

Step 4: Scenario A result = dp[2] = 4.

Scenario B: houses = [2, 3, 1] (indices 1 to 3)

Step 5: dp[0] = 2 (rob house 1).

Step 6: dp[1] = max(dp[0], nums[1]) = max(2, 3) = 3. Robbing house 2 alone is better.

Step 7: dp[2] = max(dp[1], dp[0] + nums[2]) = max(3, 2 + 1) = max(3, 3) = 3. Either way gives 3.

Step 8: Scenario B result = dp[2] = 3.

Step 9: Final answer = max(4, 3) = 4.

DP Array — Building the Solution Bottom-Up — Watch how the DP table fills from left to right. At each cell, we choose the maximum between skipping the current house (take dp[i-1]) and robbing it (take dp[i-2] + nums[i]).

Algorithm

  1. If there is only one house, return its value.
  2. Define a helper function robLinear(houses) that solves the linear House Robber problem:
    a. Create a DP array of the same length as the input.
    b. Set dp[0] = houses[0].
    c. Set dp[1] = max(houses[0], houses[1]).
    d. For each subsequent house i (from 2 to end):
    • dp[i] = max(dp[i-1], dp[i-2] + houses[i]).
      e. Return dp[last].
  3. Call robLinear on houses[0..n-2] and houses[1..n-1].
  4. Return the maximum of the two results.

Code

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

private:
    int robLinear(vector<int>& nums, int start, int end) {
        int len = end - start + 1;
        if (len == 1) return nums[start];

        vector<int> dp(len);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start + 1]);

        for (int i = 2; i < len; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }
        return dp[len - 1];
    }
};
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def rob_linear(start: int, end: int) -> int:
            length = end - start + 1
            if length == 1:
                return nums[start]

            dp = [0] * length
            dp[0] = nums[start]
            dp[1] = max(nums[start], nums[start + 1])

            for i in range(2, length):
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i])

            return dp[-1]

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

    private int robLinear(int[] nums, int start, int end) {
        int len = end - start + 1;
        if (len == 1) return nums[start];

        int[] dp = new int[len];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }
        return dp[len - 1];
    }
}

Complexity Analysis

Time Complexity: O(n)

We solve two linear DP problems, each iterating through approximately n-1 houses. Each house requires O(1) work (a comparison and an addition). Total: 2 × O(n) = O(n).

Space Complexity: O(n)

We allocate a DP array of size n-1 for each linear subproblem. This space grows linearly with the input size.

Why This Approach Is Not Efficient

While the DP array approach is already O(n) in time — which is optimal — it uses O(n) extra space for the DP array. Looking at the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]), we notice that each dp[i] depends on only the two previous values: dp[i-1] and dp[i-2].

This means we do not need to store the entire DP array. We can replace it with just two variables that track the last two values, reducing space from O(n) to O(1). For n up to 100 this is not a critical optimization, but it demonstrates an important DP pattern: when only a fixed number of previous states are needed, you can optimize space by using rolling variables.

Optimal Approach - Space-Optimized Dynamic Programming

Intuition

The optimal approach takes the same DP logic but compresses the space. Instead of maintaining an entire array, we track just two values at any point:

  • prev2: The maximum money we could rob from all houses up to two houses ago.
  • prev1: The maximum money we could rob from all houses up to the previous house.

At each new house with value x, the decision is the same:

  • Rob this house: gain = prev2 + x (we skipped the previous house).
  • Skip this house: gain = prev1 (we keep whatever was best before).

Then we slide the window forward: prev2 becomes the old prev1, and prev1 becomes the max of the two choices.

Think of it like sliding a two-cell window along the houses. At each position, the window remembers just enough history to make the optimal decision for the current house.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 1]:

We solve two scenarios:

  • Scenario A: houses [1, 2, 3] (exclude last)
  • Scenario B: houses [2, 3, 1] (exclude first)

Scenario A: houses = [1, 2, 3]

Step 1: Initialize prev2 = 0, prev1 = 0.

Step 2: Process house 0 (value=1).

  • Rob: prev2 + 1 = 0 + 1 = 1.
  • Skip: prev1 = 0.
  • New prev1 = max(0, 1) = 1. prev2 = 0 (old prev1).
  • After: prev2 = 0, prev1 = 1.

Step 3: Process house 1 (value=2).

  • Rob: prev2 + 2 = 0 + 2 = 2.
  • Skip: prev1 = 1.
  • New prev1 = max(1, 2) = 2. prev2 = 1 (old prev1).
  • After: prev2 = 1, prev1 = 2.

Step 4: Process house 2 (value=3).

  • Rob: prev2 + 3 = 1 + 3 = 4.
  • Skip: prev1 = 2.
  • New prev1 = max(2, 4) = 4. prev2 = 2 (old prev1).
  • After: prev2 = 2, prev1 = 4.

Step 5: Scenario A result = prev1 = 4.

Scenario B: houses = [2, 3, 1]

Step 6: Initialize prev2 = 0, prev1 = 0.

Step 7: Process house 1 (value=2): prev2=0, prev1=2.

Step 8: Process house 2 (value=3): rob=0+3=3, skip=2. prev1=max(2,3)=3. prev2=2.

Step 9: Process house 3 (value=1): rob=2+1=3, skip=3. prev1=max(3,3)=3. prev2=3.

Step 10: Scenario B result = 3.

Step 11: Final answer = max(4, 3) = 4.

Space-Optimized DP — Rolling Two Variables — Watch how prev2 and prev1 slide along the array, maintaining just enough state to make optimal decisions. The secondary row shows the computed dp values as we go.

Algorithm

  1. If there is only one house, return its value.
  2. Define a helper function robLinear(start, end) that solves the linear problem with two rolling variables:
    a. Initialize prev2 = 0, prev1 = 0.
    b. For each house index i from start to end:
    • Compute current = max(prev1, prev2 + nums[i]).
    • Update prev2 = prev1, prev1 = current.
      c. Return prev1.
  3. Return max(robLinear(0, n-2), robLinear(1, n-1)).

Code

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

private:
    int robLinear(vector<int>& nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
};
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def rob_linear(start: int, end: int) -> int:
            prev2, prev1 = 0, 0
            for i in range(start, end + 1):
                current = max(prev1, prev2 + nums[i])
                prev2 = prev1
                prev1 = current
            return prev1

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

    private int robLinear(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the houses twice (once for each scenario), performing O(1) work per house. Total: 2 × (n-1) iterations = O(n).

Space Complexity: O(1)

We use only three variables (prev2, prev1, current) regardless of input size. Unlike the DP array approach, no extra array is allocated. This is optimal space usage for this problem.