House Robber II

Explanation & Solution

Description

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, meaning the first house is the neighbor of the last one.

Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without robbing two adjacent houses.

Input:nums = [2,3,2]

Output: 3

Explanation: You cannot rob house 0 (money = 2) and house 2 (money = 2), because they are adjacent in the circle. The best is to rob house 1 (money = 3).

Constraints

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

Approach

Dynamic Programming pattern

1. Understand the Circular Constraint

Houses are arranged in a circle, so the first and last houses are adjacent
You cannot rob both nums[0] and nums[n - 1]

2. Break Into Two Linear Problems

Case A: Rob from house 0 to house n - 2 (exclude the last house)
Case B: Rob from house 1 to house n - 1 (exclude the first house)
The answer is max(Case A, Case B)
This works because in any valid solution, you either skip the first house, skip the last house, or skip both

3. Solve Each Linear Subproblem

Use the same approach as House Robber I
For each house i, decide to rob (prev2 + nums[i]) or skip (prev1)
Track only two variables for O(1) space

4. Handle Edge Cases

If there is only one house, return nums[0]
If there are two houses, return max(nums[0], nums[1])

5. Return the Maximum

Take the maximum of the two linear subproblem results

Key Insight

The circular constraint is elegantly handled by reducing to two instances of the linear House Robber problem

Time

O(n)two linear passes through the array

Space

O(1)only constant extra variables used

Visualization

Input:

[2, 3, 2]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

House Robber

Coin Change