213. House Robber II - Explanation

Description

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

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

Example 1:

Input: nums = [3,4,3]

Output: 4

Explanation: You cannot rob nums[0] + nums[2] = 6 because nums[0] and nums[2] are adjacent houses. The maximum you can rob is nums[1] = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 15

Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.

Constraints:

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

Topics

Array Dynamic Programming

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of houses.

Hint 1

First, consider solving the problem to get the maximum money after robbing without the condition that 'the first and last houses are adjacent'. Can you express this using a recurrence relation? Perhaps you could draw a decision tree, as at each step, you can either rob the current house and skip the next one or skip the current house and move to the next.

Hint 2

The recurrence relation can be expressed as max(nums[i] + dfs(i + 2), dfs(i + 1)), where i is the current house and dfs is the recursive function. The base condition for this recursion would be to return 0 when i goes out of bounds. This solution results in O(2^n) time complexity because, at each recursive step, we branch into two paths. Can you think of a way to avoid recalculating the result for the same recursive call multiple times?

Hint 3

We can use memoization to store the result of a recursive function in a hash map or an array and immediately return this value when the function is called again with the same parameter values. How would you implement this? How would you solve the problem if the first and last houses are adjacent to each other? Perhaps you should consider skipping any one house between the two.

Hint 4

We can create two arrays from the given array. The first will include houses from the first house to the second-to-last house, and the second will include houses from the second house to the last house. We can run the recursive function on both arrays independently and return the maximum result between the two. Advanced techniques such as bottom-up dynamic programming can further optimize the solution.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming (1D) - The core technique for solving the linear house robber subproblems
House Robber I - This problem extends the original by adding a circular constraint
Recursion with Memoization - Understanding how to cache subproblem results for top-down DP

1. Recursion

Intuition

This is House Robber II, where houses are in a circle.
So the first and last house cannot both be robbed.

To handle the circular constraint, we split the problem into two linear cases:

Rob from house 0 to n-2 (exclude last house)
Rob from house 1 to n-1 (exclude first house)

The recursive function explores:

Skip the current house
Rob the current house and jump two steps ahead

A flag is used to ensure that if the first house is robbed, the last house is not allowed.

Finally, we take the maximum result from the two cases.

Algorithm

If there is only one house, return its value.
Define a recursive function that:
- Stops when index goes out of bounds
- Prevents robbing the last house if the first was robbed
- Chooses the max of:
  - skipping the current house
  - robbing the current house and moving two steps ahead
Run recursion in two scenarios:
- Start from index 0 (first house considered)
- Start from index 1 (first house skipped)
Return the maximum of both results.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        def dfs(i, flag):
            if i >= len(nums) or (flag and i == len(nums) - 1):
                return 0

            return max(dfs(i + 1, flag),
                       nums[i] + dfs(i + 2, flag or i == 0))
        return max(dfs(0, True), dfs(1, False))

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(dfs(0, true, nums), dfs(1, false, nums));
    }

    private int dfs(int i, boolean flag, int[] nums) {
        if (i >= nums.length || (flag && i == nums.length - 1))
            return 0;

        return Math.max(dfs(i + 1, flag, nums),
                        nums[i] + dfs(i + 2, flag || i == 0, nums));
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        if (nums.length === 1) return nums[0];

        const dfs = (i, flag) => {
            if (i >= nums.length || (flag && i === nums.length - 1)) return 0;

            return Math.max(
                dfs(i + 1, flag),
                nums[i] + dfs(i + 2, flag || i === 0),
            );
        };

        return Math.max(dfs(0, true), dfs(1, false));
    }
}

public class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 1) return nums[0];
        return Math.Max(Dfs(0, true, nums), Dfs(1, false, nums));
    }

    private int Dfs(int i, bool flag, int[] nums) {
        if (i >= nums.Length || (flag && i == nums.Length - 1))
            return 0;

        return Math.Max(Dfs(i + 1, flag, nums),
                        nums[i] + Dfs(i + 2, flag || i == 0, nums));
    }
}

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    var dfs func(i int, flag bool) int
    dfs = func(i int, flag bool) int {
        if i >= len(nums) || (flag && i == len(nums)-1) {
            return 0
        }
        return max(dfs(i+1, flag), nums[i] + dfs(i+2, flag || i == 0))
    }
    return max(dfs(0, true), dfs(1, false))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        if (n == 1) return nums[0]
        fun dfs(i: Int, flag: Boolean): Int {
            if (i >= nums.size || (flag && i == nums.size - 1)) {
                return 0
            }
            return maxOf(dfs(i + 1, flag),
                         nums[i] + dfs(i + 2, flag || i == 0))
        }
        return maxOf(dfs(0, true), dfs(1, false))
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }

        func dfs(_ i: Int, _ flag: Bool) -> Int {
            if i >= nums.count || (flag && i == nums.count - 1) {
                return 0
            }
            return max(dfs(i + 1, flag), nums[i] + dfs(i + 2, flag || i == 0))
        }

        return max(dfs(0, true), dfs(1, false))
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

This is House Robber II (circular houses) with Top-Down DP.

Because houses form a circle, the first and last houses cannot both be robbed.
We handle this by tracking a flag that tells us whether the first house was robbed.

At each house, we have two choices:

Skip the house
Rob the house (then skip the next one)

Memoization is used so each state (index, flag) is solved only once.

Algorithm

If there is only one house, return its value.
Use a DP table memo[index][flag]:
- index -> current house
- flag -> whether the first house was robbed
Define a recursive function:
- Stop if index is out of bounds
- Stop if trying to rob the last house while the first was already robbed
At each step, compute:
- Max of skipping the house
- Robbing the house and jumping two steps
Run two cases:
- Start from house 0 (first house included)
- Start from house 1 (first house excluded)
Return the maximum of both cases.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        memo = [[-1] * 2 for _ in range(len(nums))]

        def dfs(i, flag):
            if i >= len(nums) or (flag and i == len(nums) - 1):
                return 0
            if memo[i][flag] != -1:
                return memo[i][flag]
            memo[i][flag] = max(dfs(i + 1, flag),
                            nums[i] + dfs(i + 2, flag or (i == 0)))
            return memo[i][flag]

        return max(dfs(0, True), dfs(1, False))

public class Solution {
    private int[][] memo;

    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        memo = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            memo[i][0] = -1;
            memo[i][1] = -1;
        }

        return Math.max(dfs(0, 1, nums), dfs(1, 0, nums));
    }

    private int dfs(int i, int flag, int[] nums) {
        if (i >= nums.length || (flag == 1 && i == nums.length - 1))
            return 0;
        if (memo[i][flag] != -1)
            return memo[i][flag];
        memo[i][flag] = Math.max(dfs(i + 1, flag, nums),
                        nums[i] + dfs(i + 2, flag | (i == 0 ? 1 : 0), nums));
        return memo[i][flag];
    }
}

class Solution {
    vector<vector<int>> memo;

public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];

        memo.resize(nums.size(), vector<int>(2, -1));
        return max(dfs(0, 1, nums), dfs(1, 0, nums));
    }

private:
    int dfs(int i, int flag, vector<int>& nums) {
        if (i >= nums.size() || (flag == 1 && i == nums.size() - 1))
            return 0;
        if (memo[i][flag] != -1)
            return memo[i][flag];
        memo[i][flag] = max(dfs(i + 1, flag, nums),
                        nums[i] + dfs(i + 2, flag | (i == 0 ? 1 : 0), nums));
        return memo[i][flag];
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        if (nums.length === 1) return nums[0];

        const n = nums.length;
        const memo = Array.from({ length: n }, () => Array(2).fill(-1));

        const dfs = (i, flag) => {
            if (i >= n || (flag && i === n - 1)) return 0;
            if (memo[i][flag] !== -1) return memo[i][flag];

            memo[i][flag] = Math.max(
                dfs(i + 1, flag),
                nums[i] + dfs(i + 2, flag | (i === 0)),
            );
            return memo[i][flag];
        };

        return Math.max(dfs(0, 1), dfs(1, 0));
    }
}

public class Solution {
    private int[][] memo;

    public int Rob(int[] nums) {
        if (nums.Length == 1) return nums[0];

        memo = new int[nums.Length][];
        for (int i = 0; i < nums.Length; i++) {
            memo[i] = new int[] { -1, -1 };
        }

        return Math.Max(Dfs(0, 1, nums), Dfs(1, 0, nums));
    }

    private int Dfs(int i, int flag, int[] nums) {
        if (i >= nums.Length || (flag == 1 && i == nums.Length - 1))
            return 0;
        if (memo[i][flag] != -1)
            return memo[i][flag];
        memo[i][flag] = Math.Max(Dfs(i + 1, flag, nums),
                        nums[i] + Dfs(i + 2, flag | (i == 0 ? 1 : 0), nums));
        return memo[i][flag];
    }
}

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 1) return nums[0]
        val memo = Array(nums.size) { IntArray(2) { -1 } }

        fun dfs(i: Int, flag: Int): Int {
            if (i >= nums.size || (flag == 1 && i == nums.size - 1)) {
                return 0
            }
            if (memo[i][flag] != -1) {
                return memo[i][flag]
            }
            memo[i][flag] = maxOf(dfs(i + 1, flag),
                                  nums[i] + dfs(i + 2, flag or if (i == 0) 1 else 0))
            return memo[i][flag]
        }

        return maxOf(dfs(0, 1), dfs(1, 0))
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }

        var memo = Array(repeating: Array(repeating: -1, count: 2), count: nums.count)

        func dfs(_ i: Int, _ flag: Bool) -> Int {
            if i >= nums.count || (flag && i == nums.count - 1) {
                return 0
            }
            if memo[i][flag ? 1 : 0] != -1 {
                return memo[i][flag ? 1 : 0]
            }

            memo[i][flag ? 1 : 0] = max(
                dfs(i + 1, flag), nums[i] + dfs(i + 2, flag || i == 0)
            )

            return memo[i][flag ? 1 : 0]
        }

        return max(dfs(0, true), dfs(1, false))
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

This is House Robber II (circular houses) solved using Bottom-Up Dynamic Programming.

Because houses are in a circle, you cannot rob both the first and last house.
So we split the problem into two linear cases:

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

Each case becomes the normal House Robber I problem.

Algorithm

If there is only one house, return its value.
Solve two cases:
- Case 1: Rob houses nums[1:]
- Case 2: Rob houses nums[:-1]
For each case, use bottom-up DP:
- dp[i] = maximum money up to house i
- Transition:
```
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
```
Return the maximum of both cases.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        return max(self.helper(nums[1:]),
                   self.helper(nums[:-1]))

    def helper(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

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

        return dp[-1]

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        return Math.max(helper(Arrays.copyOfRange(nums, 1, nums.length)),
                        helper(Arrays.copyOfRange(nums, 0, nums.length - 1)));
    }

    private int helper(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

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

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

        return dp[nums.length - 1];
    }
}

class Solution {
public:
    int rob(std::vector<int>& nums) {
        if (nums.size() == 1) return nums[0];

        return max(helper(vector<int>(nums.begin() + 1, nums.end())),
                        helper(vector<int>(nums.begin(), nums.end() - 1)));
    }

    int helper(vector<int> nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

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

        return dp.back();
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        if (nums.length === 0) return 0;
        if (nums.length === 1) return nums[0];

        return Math.max(
            this.helper(nums.slice(1)),
            this.helper(nums.slice(0, -1)),
        );
    }

    /**
     * @param {number[]} nums
     * @return {number}
     */
    helper(nums) {
        if (nums.length === 0) return 0;
        if (nums.length === 1) return nums[0];

        const dp = new Array(nums.length);
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (let i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.length - 1];
    }
}

public class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];

        return Math.Max(Helper(nums[1..]), Helper(nums[..^1]));
    }

    private int Helper(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];

        int[] dp = new int[nums.Length];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);

        for (int i = 2; i < nums.Length; i++) {
            dp[i] = Math.Max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[^1];
    }
}

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 1) {
            return nums[0]
        }
        return max(helper(nums.copyOfRange(1, nums.size)),
                   helper(nums.copyOfRange(0, nums.size - 1)))
    }

    fun helper(nums: IntArray): Int {
        if (nums.isEmpty()) {
            return 0
        }
        if (nums.size == 1) {
            return nums[0]
        }

        val dp = IntArray(nums.size)
        dp[0] = nums[0]
        dp[1] = maxOf(nums[0], nums[1])

        for (i in 2 until nums.size) {
            dp[i] = maxOf(dp[i - 1], nums[i] + dp[i - 2])
        }

        return dp[nums.size - 1]
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }
        return max(helper(Array(nums[1...])), helper(Array(nums[..<(nums.count - 1)])))
    }

    func helper(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        if nums.count == 1 {
            return nums[0]
        }

        var dp = [Int](repeating: 0, count: nums.count)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in 2..<nums.count {
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
        }

        return dp.last!
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized)

Intuition

This is House Robber II, where houses are arranged in a circle.
Because of the circular setup, you cannot rob both the first and last house.

To handle this, split the problem into two linear subproblems:

Rob houses excluding the first house.
Rob houses excluding the last house.

Each subproblem becomes the classic House Robber I, which can be solved using two variables instead of a full DP array.

Algorithm

If there is only one house, return its value.
Compute the maximum money for:
- Houses nums[1:] (skip first)
- Houses nums[:-1] (skip last)
For each linear list:
- Maintain two variables:
  - rob1 -> best up to house i-2
  - rob2 -> best up to house i-1
- For each house:
```
newRob = max(rob1 + current_house, rob2)
rob1 = rob2
rob2 = newRob
```
Return the maximum of the two cases.

class Solution:

    def rob(self, nums: List[int]) -> int:
        return max(nums[0], self.helper(nums[1:]),
                            self.helper(nums[:-1]))

    def helper(self, nums):
        rob1, rob2 = 0, 0

        for num in nums:
            newRob = max(rob1 + num, rob2)
            rob1 = rob2
            rob2 = newRob
        return rob2

public class Solution {

    public int rob(int[] nums) {
        return Math.max(nums[0],
               Math.max(helper(Arrays.copyOfRange(nums, 1, nums.length)),
               helper(Arrays.copyOfRange(nums, 0, nums.length - 1))));
    }

    private int helper(int[] nums) {
        int rob1 = 0, rob2 = 0;

        for (int num : nums) {
            int newRob = Math.max(rob1 + num, rob2);
            rob1 = rob2;
            rob2 = newRob;
        }
        return rob2;
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        return Math.max(
            nums[0],
            Math.max(
                this.helper(nums.slice(1)),
                this.helper(nums.slice(0, -1)),
            ),
        );
    }

    /**
     * @param {number[]} nums
     * @return {number}
     */
    helper(nums) {
        let rob1 = 0;
        let rob2 = 0;
        for (const num of nums) {
            const newRob = Math.max(rob1 + num, rob2);
            rob1 = rob2;
            rob2 = newRob;
        }
        return rob2;
    }
}

public class Solution {

    public int Rob(int[] nums) {
        if (nums.Length == 1)
            return nums[0];

        return Math.Max(Helper(nums[1..]),
                        Helper(nums[..^1]));
    }

    private int Helper(int[] nums) {
        int rob1 = 0, rob2 = 0;
        foreach (int num in nums) {
            int newRob = Math.Max(rob1 + num, rob2);
            rob1 = rob2;
            rob2 = newRob;
        }
        return rob2;
    }
}

class Solution {
    fun rob(nums: IntArray): Int {
        return maxOf(nums[0],
            maxOf(helper(nums.copyOfRange(1, nums.size)),
            helper(nums.copyOfRange(0, nums.size - 1))))
    }

    private fun helper(nums: IntArray): Int {
        var rob1 = 0
        var rob2 = 0

        for (num in nums) {
            val newRob = maxOf(rob1 + num, rob2)
            rob1 = rob2
            rob2 = newRob
        }
        return rob2
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        if nums.count == 1 {
            return nums[0]
        }

        let candidate1 = nums[0]
        let candidate2 = helper(Array(nums[1..<nums.count]))
        let candidate3 = helper(Array(nums[0..<(nums.count - 1)]))

        return max(max(candidate1, candidate2), candidate3)
    }

    func helper(_ nums: [Int]) -> Int {
        var rob1 = 0
        var rob2 = 0

        for num in nums {
            let newRob = max(rob1 + num, rob2)
            rob1 = rob2
            rob2 = newRob
        }

        return rob2
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting the Single House Edge Case

When there is only one house, the circular constraint does not apply since there is no adjacency conflict. If you split the problem into nums[1:] and nums[:-1] without handling this case, both subarrays become empty when n=1, and the function returns 0 instead of nums[0]. Always check if the array has only one element and return its value directly.

Incorrectly Handling the Circular Constraint

The key insight is that the first and last houses cannot both be robbed. A common mistake is to add complex flag logic throughout the recursion when a simpler approach exists: run the standard House Robber algorithm twice, once excluding the first house and once excluding the last house. Taking the maximum of these two results correctly handles the circular dependency without overcomplicating the code.

Off-by-One Errors in Array Slicing

When splitting the array into nums[1:] (exclude first) and nums[:-1] (exclude last), be careful with language-specific slicing syntax. In some languages, you need to manually copy subarrays or adjust loop bounds. An off-by-one error here can lead to including both the first and last houses in one subproblem, or excluding more houses than intended, producing incorrect results.