House Robber II | Leetcode 213 | All 4 Solutions

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.

Here’s the [Problem Link] to begin with.

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

How Does the “Circular” Constraint Change Things?

In the original House Robber, you could simply decide “rob or skip” for each house, moving linearly. Now, if you rob the first house, you can’t rob the last, and vice versa.
So, split into two scenarios:

1. Rob houses 0 to n-2 (skip the last house).
2. Rob houses 1 to n-1 (skip the first house).

Take the maximum of the two.
Let’s apply different DP approaches for each scenario.

Solution 1: Brute Force (Recursion)

Intuition

At every step, you have two choices:

• Pick the current house (and thus skip the previous one)
• Skip the current house (and take the best from earlier)

Because of the circular nature, we run the logic twice:

• Once excluding the last house (nums[0 : n-1])
• Once excluding the first house (nums[1 : n])

Take the max of both results.

Detailed Approach

• Base Cases:
  • If index == 0: Only one house, so rob it.
  • If index == -1: No houses left, so rob nothing.
• Recursive Cases:
  • pick = nums[index] + solve(index-2, nums)
  • notpick = solve(index-1, nums)
  • Return max(pick, notpick)
• Do this for both possible slices.

Code

class Solution:
    def solve(self, index, nums):
        # If only one house left, rob it
        if index == 0:
            return nums[index]
        # If no houses left, rob nothing
        if index == -1:
            return 0
        # Option 1: Pick current house and move two steps back
        pick = nums[index] + self.solve(index - 2, nums)
        # Option 2: Skip current house and move one step back
        notpick = self.solve(index - 1, nums)
        # Return max loot possible at this index
        return max(pick, notpick)
    
    def rob(self, nums: List[int]) -> int:
        # Base case: only one house (no circle constraint)
        if len(nums) == 1:
            return nums[0]
        n = len(nums)
        # Scenario 1: Rob from 0 to n-2
        ans1 = self.solve(n - 2, nums[0 : n - 1])
        # Scenario 2: Rob from 1 to n-1
        ans2 = self.solve(n - 2, nums[1 : n])
        # Return the best out of both possibilities
        return max(ans1, ans2)

Code Explanation

• solve(index, nums) recursively computes the best you can do for a slice.
• Careful splitting ensures the circle is not broken (never include both first and last house).
• Calls solve for both scenarios, returns the maximum possible loot.

Time and Space Complexity

• Time: O(2^n) – Each call can branch into two subproblems; exponential.
• Space: O(n) – Due to recursion stack.

Simplifying It

Think: You’re trying every possible rob/skip path for both possible ranges, but you forget the results of previous calculations. Practical only for small n.

Solution 2: Memoization (Top-Down DP)

Intuition

In brute force, the same subproblems are recalculated many times. Memoization adds a DP array to remember results for each index and subarray. Same two scenarios apply (exclude first, exclude last); now we save time by caching.

Detailed Approach

• DP array of length n-1 (as we slice nums to length n-1 each time).
• For each call, if value already computed (dp[index] != -1), return cached result.
• Otherwise, compute as with recursion and store result in dp array.

Code

class Solution:
    def solve(self, index, nums, dp):
        # If only one house left, rob it
        if index == 0:
            return nums[index]
        # If no houses left
        if index == -1:
            return 0
        # Use cached value if available
        if dp[index] != -1:
            return dp[index]
        # Option 1: Pick and add result from index-2
        pick = nums[index] + self.solve(index - 2, nums, dp)
        # Option 2: Skip current house
        notpick = self.solve(index - 1, nums, dp)
        dp[index] = max(pick, notpick)
        return dp[index]
    
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        n = len(nums)
        # Rob from 0 to n-2
        dp1 = [-1] * (n - 1)
        ans1 = self.solve(n - 2, nums[0 : n - 1], dp1)
        # Rob from 1 to n-1
        dp2 = [-1] * (n - 1)
        ans2 = self.solve(n - 2, nums[1 : n], dp2)
        return max(ans1, ans2)

Code Explanation

• Like pure recursion, but now each subproblem is solved just once, thanks to the dp array.
• Both slices (nums[0:n-1] and nums[1:n]) use separate dp arrays, ensuring circle constraint is always satisfied.

Time and Space Complexity

• Time: O(n) per subarray (n-1), so O(n) total.
• Space: O(n) for DP arrays + O(n) for stack frames.

Simplifying It

Now you keep a notebook for each scenario and never recalculate any decision. Much faster, good for large n!

Solution 3: Tabulation (Bottom-Up DP)

Intuition

Instead of starting from end and recursing, fill up DP array from base to target using a for-loop. For each index, loot = max(current house + dp[index-2], dp[index-1]).

Detailed Approach

• For each scenario (exclude last or exclude first), make separate pass.
• Start with dp = nums
• For each index,
  • If index > 1:
    pick = nums[index] + dp[index-2]
  • Else:
    pick = nums[index]
  • not_pick = dp[index-1]
  • dp[index] = max(pick, not_pick)

Code

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [-1] * n
        dp[0] = nums[0]
        for index in range(1, n):
            # Pick current + two steps back if possible
            if index > 1:
                pick = nums[index] + dp[index - 2]
            else:
                pick = nums[index]
            # Skip current, take previous result
            not_pick = dp[index - 1]
            dp[index] = max(pick, not_pick)
        return dp[n - 1]
    
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        # Exclude last and exclude first scenarios
        ans1 = self.solve(nums[0 : n - 1])
        ans2 = self.solve(nums[1 : n])
        return max(ans1, ans2)

Code Explanation

• The solve function fills dp array from left to right, building up possibilities step by step.
• Main rob function checks for the single house case; otherwise, runs both possible cases.

Time and Space Complexity

• Time: O(n) per scenario, so O(n) total.
• Space: O(n) for dp array.

Simplifying It

You write a plan for each possible chain of houses, filling the results for each step, and never look back!

Solution 4: Space-Optimized Tabulation (Best Practice)

Intuition

While building the dp array, we only ever need the last two values. Replace array with two variables (prev, prev2) for memory efficiency; great for interviews!

Detailed Approach

• For each slice, initialize:
  • prev as the value at index 0 (nums)
  • prev2 to 0
• For each house, update:
  • If index > 1:
    • pick = nums[index] + prev2
  • Else:
    • pick = nums[index]
  • not_pick = prev
  • curr = max(pick, not_pick)
  • Slide window: prev2 = prev; prev = curr

Code

class Solution:
    def solve(self, nums):
        n = len(nums)
        prev = nums[0]   # DP for index - 1
        prev2 = 0        # DP for index - 2
        for index in range(1, n):
            # Pick current house and add loot from two steps back
            if index > 1:
                pick = nums[index] + prev2
            else:
                pick = nums[index]
            # Skip current house, use prev result
            not_pick = prev
            curr = max(pick, not_pick)
            # Update window
            prev2 = prev
            prev = curr
        return prev
    
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        # Try both scenarios (excluding first or last house)
        ans1 = self.solve(nums[0 : n - 1])
        ans2 = self.solve(nums[1 : n])
        return max(ans1, ans2)

Code Explanation

• Only two variables needed throughout; for each scenario, make a linear scan.
• Final answer is the better loot from both scenarios, so the circle is always respected.

Time and Space Complexity

• Time: O(n)
• Space: O(1) (just variables, not arrays)

Simplifying It

It’s like moving through the houses with a calculator, only tracking the last two amounts, always keeping memory and speed at max efficiency!

Summary Table

Conclusion

The House Robber II problem is a powerful demonstration of how a small twist (the circular street) can change a familiar dynamic programming pattern. Start with recursion for clarity, move through memoization and tabulation, and finish with sleek space optimization for interviews or production code. Practice with variants like “House Robber I” and related DP problems to reinforce your foundations.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.