LeetCode 213 - House Robber II

LeetCode Problem 213

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem is a variation of the classic House Robber dynamic programming problem, with one important twist: the houses are arranged in a circle rather than a straight line.

We are given an integer array nums, where each element represents the amount of money available in a house. The goal is to determine the maximum amount of money that can be robbed in a single night without triggering the alarm system.

The restriction is that adjacent houses cannot both be robbed. If two neighboring houses are robbed, the police are alerted.

In the original House Robber problem, the houses form a straight line, meaning only immediate left and right neighbors matter. Here, however, the houses form a circular arrangement, which introduces an additional constraint:

• The first house and the last house are also neighbors.
• This means we cannot rob both nums[0] and nums[n - 1].

The input consists of:

• nums, an integer array where:

• nums[i] represents the money in the i-th house.

• nums.length is between 1 and 100.

• Each house contains between 0 and 1000 dollars.

The output is a single integer representing the maximum money that can be robbed without violating adjacency constraints.

The constraints are relatively small, only up to 100 houses, meaning even an O(n²) solution could technically work. However, this problem is designed to test dynamic programming reasoning, and an optimal linear solution is expected.

Several edge cases are important to consider upfront.

If there is only one house, then there are no neighbors to worry about, and we simply rob that house.

If there are two houses, since they are adjacent in the circle, we can only rob one of them.

Another tricky case occurs because of the circular layout. A naive implementation of the original House Robber logic might accidentally rob both the first and last houses, which would violate the rules. Handling this correctly is the central challenge of the problem.

Approaches

Brute Force Approach

The brute force approach explores every possible subset of houses and checks whether it forms a valid robbery plan.

For each house, we have two choices:

1. Rob it.
2. Skip it.

This creates a recursive decision tree with roughly 2^n possibilities. At every step, we ensure no adjacent houses are selected, including the circular adjacency between the first and last houses.

This method guarantees correctness because it exhaustively evaluates every valid robbery combination and returns the maximum total amount.

However, it is far too slow. Since every house doubles the number of possibilities, the runtime becomes exponential, making it impractical as n grows.

Key Insight for an Optimal Solution

The key observation is that the circular arrangement creates only one extra restriction compared to the original House Robber problem:

We cannot rob both the first and last house.

This means every valid solution falls into exactly one of two categories:

1. Exclude the first house, allowing us to freely consider the last house.
2. Exclude the last house, allowing us to freely consider the first house.

Once we make this choice, the problem becomes the original linear House Robber problem.

For a linear street of houses, we use dynamic programming:

For each house, we decide:

• Rob this house and add its value to the best result from two houses back.
• Skip this house and keep the previous best result.

The recurrence is:

$$dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$$

Instead of storing an entire DP array, we only need the previous two states, reducing space complexity to O(1).

We compute:

• Maximum robbery for nums[1:] (skip first)
• Maximum robbery for nums[:-1] (skip last)

Then take the maximum of those two results.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores every valid robbery combination
Optimal	O(n)	O(1)	Splits circle into two linear robber problems

Algorithm Walkthrough

1. Handle the single-house edge case

If nums contains only one house, return its value immediately. Since there are no neighbors, robbing it never violates the rules. 2. Define a helper function for the linear version

Create a helper function that solves the original House Robber problem for a straight line of houses.

This function keeps track of two values:

• prev_two, the best amount from two houses ago.
• prev_one, the best amount from the previous house.

For each house, compute:

current = max(prev_one, prev_two + house_value)

This means:

• Skip the current house and keep the previous best result.
• Rob the current house and add it to the best result from two positions back.

3. Solve the two valid scenarios

Because the first and last houses cannot both be robbed, compute:

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

Each of these is now a standard linear House Robber problem. 4. Return the better result

Take the maximum of the two scenarios.

This guarantees the answer respects the circular constraint while still maximizing profit.

Why it works

Every valid robbery plan must exclude either the first house or the last house, because robbing both is illegal in a circle. By solving both possibilities independently, we cover all valid solutions without overlap. The helper function correctly computes the optimal robbery amount for a linear arrangement using dynamic programming, where each state represents the best achievable result up to that point. Taking the maximum of the two linear cases guarantees the globally optimal solution.

Python Solution

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob_linear(houses: List[int]) -> int:
            prev_two = 0
            prev_one = 0

            for money in houses:
                current = max(prev_one, prev_two + money)
                prev_two = prev_one
                prev_one = current

            return prev_one

        if len(nums) == 1:
            return nums[0]

        exclude_last = rob_linear(nums[:-1])
        exclude_first = rob_linear(nums[1:])

        return max(exclude_last, exclude_first)

The implementation begins by defining a helper function, rob_linear, which solves the standard House Robber problem for a straight street of houses.

Inside this helper, we avoid using a full dynamic programming array. Instead, we maintain only two variables:

• prev_two, representing the best result up to two houses ago.
• prev_one, representing the best result up to the previous house.

For every house, we compute the best possible result if we either rob or skip that house. The variable current stores this decision:

max(prev_one, prev_two + money)

After computing the current state, we shift the variables forward so they represent the next iteration.

Outside the helper function, we first handle the edge case where there is only one house.

Then we evaluate the two valid circular scenarios:

• Excluding the last house using nums[:-1]
• Excluding the first house using nums[1:]

Since these are now linear arrangements, we apply the helper function to both and return the larger result.

Go Solution

func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	robLinear := func(houses []int) int {
		prevTwo := 0
		prevOne := 0

		for _, money := range houses {
			current := max(prevOne, prevTwo+money)
			prevTwo = prevOne
			prevOne = current
		}

		return prevOne
	}

	excludeLast := robLinear(nums[:len(nums)-1])
	excludeFirst := robLinear(nums[1:])

	return max(excludeLast, excludeFirst)
}

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

The Go implementation follows the same algorithmic structure as the Python version. A local helper function, robLinear, solves the linear version of the problem using constant extra space.

One Go-specific difference is that Go does not provide a built-in max function for integers, so we define a helper manually.

Slicing is used to create the two valid subproblems:

• nums[:len(nums)-1] excludes the last house.
• nums[1:] excludes the first house.

Since the problem guarantees at least one house exists, we only need to explicitly handle the len(nums) == 1 case.

Go slices are lightweight views into the underlying array, so creating subranges does not copy the data, making this approach efficient.

Worked Examples

Example 1

Input:

nums = [2,3,2]

We solve two scenarios.

Scenario 1: Exclude Last House

Array becomes:

[2,3]

House Value	prev_two	prev_one	current
2	0	0	2
3	0	2	3

Result = 3

Scenario 2: Exclude First House

Array becomes:

[3,2]

House Value	prev_two	prev_one	current
3	0	0	3
2	0	3	3

Result = 3

Final answer:

max(3, 3) = 3

Example 2

Input:

nums = [1,2,3,1]

Scenario 1: Exclude Last House

Array:

[1,2,3]

House Value	prev_two	prev_one	current
1	0	0	1
2	0	1	2
3	1	2	4

Result = 4

Scenario 2: Exclude First House

Array:

[2,3,1]

House Value	prev_two	prev_one	current
2	0	0	2
3	0	2	3
1	2	3	3

Result = 3

Final answer:

max(4, 3) = 4

Example 3

Input:

nums = [1,2,3]

Scenario 1: Exclude Last House

Array:

[1,2]

House Value	prev_two	prev_one	current
1	0	0	1
2	0	1	2

Result = 2

Scenario 2: Exclude First House

Array:

[2,3]

House Value	prev_two	prev_one	current
2	0	0	2
3	0	2	3

Result = 3

Final answer:

max(2, 3) = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We solve two linear robber problems, each scanning the array once
Space	O(1)	Only a few variables are maintained regardless of input size

Although we run the linear robbery algorithm twice, each pass is proportional to n, so the total runtime remains O(n). The helper function stores only two previous DP states, meaning extra memory usage stays constant.

Test Cases

solution = Solution()

assert solution.rob([2, 3, 2]) == 3  # Example 1
assert solution.rob([1, 2, 3, 1]) == 4  # Example 2
assert solution.rob([1, 2, 3]) == 3  # Example 3

assert solution.rob([5]) == 5  # Single house
assert solution.rob([2, 7]) == 7  # Two adjacent houses
assert solution.rob([1, 1, 1, 1]) == 2  # Equal values
assert solution.rob([100, 1, 1, 100]) == 101  # First and last cannot both be robbed
assert solution.rob([0, 0, 0]) == 0  # All zero values
assert solution.rob([1, 3, 1, 3, 100]) == 103  # Large value at end
assert solution.rob([200, 3, 140, 20, 10]) == 340  # Larger mixed case
assert solution.rob([1, 2, 1, 1]) == 3  # Multiple optimal paths

Test	Why
[2,3,2]	Verifies circular adjacency constraint
[1,2,3,1]	Standard example with optimal skipping
[1,2,3]	Ensures correct circular handling
[5]	Single house edge case
[2,7]	Two-house circular edge case
[1,1,1,1]	Equal-value houses
[100,1,1,100]	Ensures first and last cannot both be robbed
[0,0,0]	Handles zero values correctly
[1,3,1,3,100]	Tests preference for larger distant values
[200,3,140,20,10]	Mixed-value dynamic programming case
[1,2,1,1]	Confirms correctness when multiple valid solutions exist

Edge Cases

Single House

When nums = [x], the first and last house are technically the same house. A buggy implementation might try to split the problem into nums[:-1] and nums[1:], producing empty arrays and returning 0. The implementation explicitly checks for len(nums) == 1 and immediately returns the house value.

First and Last House Conflict

A common mistake is applying the original House Robber algorithm directly to the circular array. For example:

[100, 1, 1, 100]

A linear solution would incorrectly choose both 100 values for 200, but those houses are adjacent in the circle. By solving two separate scenarios, excluding either the first or last house, the implementation avoids illegal combinations and correctly returns 101.

Two Houses

When there are exactly two houses, both are adjacent because of the circle. A careless implementation may accidentally treat them independently and sum both values. Instead, the split naturally becomes:

nums[:-1]
nums[1:]

Each contains only one house, and the algorithm correctly returns the maximum of the two values.