LeetEye LeetEye
Medium 1D Dynamic Programming ~5 min

House Robber II

1d-dp house-robber-ii

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.

Examples

Example 1
Input: nums = [2,3,2]
Output: 3
Cannot rob house 0 and 2 (adjacent in circle). Rob house 1.
Example 2
Input: nums = [1,2,3,1]
Output: 4
Rob house 0 (1) + house 2 (3) = 4
Key Insight

Break the circle: either skip the first house OR skip the last house. Solve two linear problems.

Circle = first and last adjacent. Break it: max(rob houses 0 to n-2, rob houses 1 to n-1). Solve two linear House Robber problems.

How to Approach This Problem

Pattern Recognition: When you see keywords like house robber ii 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 In a circle, houses 0 and n-1 are:
Answer: Adjacent (can't both be robbed)
Circle means first and last are neighbors.
2 We can split this into:
Answer: Consider houses [0, n-2] OR [1, n-1]
If we exclude last house, first can be robbed. If we exclude first, last can be robbed. One of these is optimal.
3 max(rob[0..n-2], rob[1..n-1]) is correct because:
Answer: One range includes first, other includes last
[0..n-2] allows robbing first but not last. [1..n-1] allows robbing last but not first. The optimal answer falls into one of these.
4 Middle houses (not first or last):
Answer: Are in both ranges
Both ranges include middle houses. They can be robbed in either scenario.
5 With only one house:
Answer: Return nums[0]
One house has no neighbors (including itself). Rob it.

Solution

def rob(nums: List[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    
    def rob_linear(houses):
        prev2, prev1 = 0, 0
        for money in houses:
            curr = max(money + prev2, prev1)
            prev2 = prev1
            prev1 = curr
        return prev1
    
    # Skip last house OR skip first house
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye