# House Robber II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/house-robber-ii)
Canonical: https://scaleengineer.com/dsa/problems/house-robber-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Docusign](https://scaleengineer.com/companies/docusign), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Visa](https://scaleengineer.com/companies/visa), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [Nordstrom](https://scaleengineer.com/companies/nordstrom), [thoughtspot](https://scaleengineer.com/companies/thoughtspot), [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
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**_.

**Example 1:**

**Input:** nums = [2,3,2]
**Output:** 3
**Explanation:** You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

**Example 2:**

**Input:** nums = [1,2,3,1]
**Output:** 4
**Explanation:** Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

**Example 3:**

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

**Constraints:**

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

# Approaches
## Recursive Approach
Use recursion to explore all possible combinations of houses that can be robbed without alerting the police, considering the circular arrangement.
**Time:** O(2^n) - where n is the length of the array, as we make two recursive calls for each element · **Space:** O(n) - due to the recursive call stack
**Pros:** Simple and intuitive approach; Easy to understand and implement
**Cons:** Exponential time complexity makes it inefficient for larger inputs; Redundant calculations of same subproblems; Can cause stack overflow for large inputs
### Explanation
This approach uses recursion to solve the problem by considering two cases for each house - either rob it or skip it. Since the houses are arranged in a circle, we need to handle the first and last house separately to avoid robbing adjacent houses.

```java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(
            robHelper(nums, 0, nums.length - 2),
            robHelper(nums, 1, nums.length - 1)
        );
    }
    
    private int robHelper(int[] nums, int start, int end) {
        if (start > end) return 0;
        if (start == end) return nums[start];
        
        return Math.max(
            nums[start] + robHelper(nums, start + 2, end),
            robHelper(nums, start + 1, end)
        );
    }
}
```
### Algorithm
1. If array is empty, return 0
2. If array has only one element, return that element
3. For each position:
   - Consider two subarrays: one excluding the last element and another excluding the first element
   - For each subarray, recursively calculate:
     * Maximum money if current house is robbed (skip next house)
     * Maximum money if current house is skipped (consider next house)
4. Return maximum of the two subarray results

## Dynamic Programming with Memoization
Optimize the recursive solution by storing previously calculated results in a memoization array to avoid redundant calculations.
**Time:** O(n) - where n is the length of the array, as each subproblem is solved only once · **Space:** O(n) - for the memoization map and recursive call stack
**Pros:** Reduces time complexity by avoiding redundant calculations; Uses memory to store intermediate results; Still maintains the recursive structure
**Cons:** Still uses recursive calls which can lead to stack overflow; Requires additional space for memoization; Not as efficient as iterative approach
### Explanation
This approach improves the recursive solution by using memoization to store the results of subproblems. We use a HashMap to store the results of each subproblem indexed by the position.

```java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        Map<Integer, Integer> memo1 = new HashMap<>();
        Map<Integer, Integer> memo2 = new HashMap<>();
        
        return Math.max(
            robHelper(nums, 0, nums.length - 2, memo1),
            robHelper(nums, 1, nums.length - 1, memo2)
        );
    }
    
    private int robHelper(int[] nums, int start, int end, Map<Integer, Integer> memo) {
        if (start > end) return 0;
        if (start == end) return nums[start];
        if (memo.containsKey(start)) return memo.get(start);
        
        int result = Math.max(
            nums[start] + robHelper(nums, start + 2, end, memo),
            robHelper(nums, start + 1, end, memo)
        );
        
        memo.put(start, result);
        return result;
    }
}
```
### Algorithm
1. If array is empty, return 0
2. If array has only one element, return that element
3. Create two memoization maps for two subarrays
4. For each position:
   - Check if result exists in memo
   - If not, calculate and store:
     * Maximum money if current house is robbed
     * Maximum money if current house is skipped
5. Return maximum of the two subarray results

## Dynamic Programming with Iteration
Use an iterative approach with dynamic programming to calculate the maximum amount that can be robbed, considering the circular arrangement of houses.
**Time:** O(n) - where n is the length of the array, as we iterate through the array twice · **Space:** O(1) - only uses three variables regardless of input size
**Pros:** Most efficient solution with linear time complexity; No recursion, so no stack overflow risk; Uses constant extra space; Faster execution compared to recursive approaches
**Cons:** Slightly more complex to understand than recursive approach; Requires careful handling of edge cases; Need to run the algorithm twice for the two subarrays
### Explanation
This approach uses dynamic programming with iteration to solve the problem. We handle the circular arrangement by running the algorithm twice - once excluding the first house and once excluding the last house. For each subarray, we maintain a dp array where dp[i] represents the maximum amount that can be robbed up to house i.

```java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        
        return Math.max(
            robRange(nums, 0, nums.length - 2),  // Exclude last house
            robRange(nums, 1, nums.length - 1)   // Exclude first house
        );
    }
    
    private int robRange(int[] nums, int start, int end) {
        int prev2 = 0;  // dp[i-2]
        int prev1 = 0;  // dp[i-1]
        int current = 0;
        
        for (int i = start; i <= end; i++) {
            current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
}
```
### Algorithm
1. Handle base cases for arrays of length 0, 1, and 2
2. For the main array, consider two subarrays:
   - One excluding the last house
   - One excluding the first house
3. For each subarray:
   - Maintain three variables for dp[i-2], dp[i-1], and current
   - For each house i:
     * Calculate maximum of (previous house, current house + house two steps back)
     * Update the variables
4. Return maximum of the two subarray results

# Solutions
### Java

```java
class Solution { public int rob ( int [] nums ) { int n = nums . length ; if ( n == 1 ) { return nums [ 0 ]; } return Math . max ( rob ( nums , 0 , n - 2 ), rob ( nums , 1 , n - 1 )); } private int rob ( int [] nums , int l , int r ) { int f = 0 , g = 0 ; for (; l <= r ; ++ l ) { int ff = Math . max ( f , g ); g = f + nums [ l ]; f = ff ; } return Math . max ( f , g ); } }
```

### CPP

```cpp
class Solution {
public:
  int rob(vector<int> &nums) {
    int n = nums.size();
    if (n == 1) {
      return nums[0];
    }
    return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
  }
  int robRange(vector<int> &nums, int l, int r) {
    int f = 0, g = 0;
    for (; l <= r; ++l) {
      int ff = max(f, g);
      g = f + nums[l];
      f = ff;
    }
    return max(f, g);
  }
};

```

### Python

```python
class Solution : def rob ( self , nums : List [ int ]) -> int : def robRange ( nums , l , r ): # re-use LC-198 solution not_rob , rob = 0 , nums [ l ] for num in nums [ l + 1 : r + 1 ]: # to include 'r' not_rob , rob = rob , max ( num + not_rob , rob ) return rob n = len ( nums ) if n == 1 : return nums [ 0 ] s1 , s2 = robRange ( nums , 0 , n - 2 ), robRange ( nums , 1 , n - 1 ) # inclusive return max ( s1 , s2 ) ############ class Solution : def rob ( self , nums : List [ int ]) -> int : def _rob ( nums ): f = g = 0 for x in nums : f , g = max ( f , g ), f + x return max ( f , g ) if len ( nums ) == 1 : return nums [ 0 ] return max ( _rob ( nums [ 1 :]), _rob ( nums [: - 1 ]))
```