House Robber II

Circular DP via two linear House Robber passes

time O(n)space O(1)

Because the houses form a circle, house 0 and house n-1 are adjacent — you can never rob both. This creates a simple split: either you rob within houses 0 to n-2 (excluding the last house), or within houses 1 to n-1 (excluding the first house). Each subproblem is an ordinary linear House Robber problem solved in O(n) using the recurrence rob[i] = max(rob[i-1], rob[i-2] + nums[i]). Taking max(robLinear(nums[0..n-2]), robLinear(nums[1..n-1])) guarantees we never rob both ends.

Details

Animated on: nums = [2, 3, 2] — houses arranged in a circle. Maximize loot without robbing adjacent houses.

Problem:House Robber IIMedium

Pattern:1D Dynamic Programming

Circular DP via two linear House Robber passes

step 1 / 8

[0]

[1]

[2]

Houses [2, 3, 2] form a circle: index 0 and index 2 are adjacent. We cannot rob both. Split into two linear sub-arrays: [2, 3] (houses 0..1) and [3, 2] (houses 1..2).

first=0· arr[0] = 2
last=2· arr[2] = 2

Pseudocode

1FUNCTION rob(nums):
2  IF the length of nums is 1: RETURN nums[0]
3  FUNCTION robLinear(arr):
4    prev2 = 0, prev1 = 0
5    FOR each x in arr:
6      cur = the larger of prev1 and prev2 + x
7      prev2 = prev1; prev1 = cur
8    RETURN prev1
9  RETURN the larger of robLinear(nums[0..n-2]) and robLinear(nums[1..n-1])

← / → step · space play · Home restart

Every step in words

Show all 8 steps

Houses [2, 3, 2] form a circle: index 0 and index 2 are adjacent. We cannot rob both. Split into two linear sub-arrays: [2, 3] (houses 0..1) and [3, 2] (houses 1..2).
Pass 1 (exclude house 2): Consider house 0 (val 2). prev2=0, prev1=0. cur = max(0, 0+2) = 2. Update prev2=0, prev1=2.
Pass 1: House 1 (val 3). cur = max(prev1=2, prev2+3 = 0+3=3) = 3. Update prev2=2, prev1=3.
Pass 1 finished: robLinear([2, 3]) = 3 (robbing house 1).
Pass 2 (exclude house 0): Consider house 1 (val 3). prev2=0, prev1=0. cur = max(0, 0+3) = 3. prev2=0, prev1=3.
Pass 2: House 2 (val 2). cur = max(prev1=3, prev2+2 = 0+2=2) = 3. Update prev2=3, prev1=3.
Pass 2 finished: robLinear([3, 2]) = 3 (robbing house 1).
Combine results: max(pass1=3, pass2=3) = 3. Robbing house 1 yields maximum loot 3 without circular conflicts.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve House Robber II in the editor All Dynamic Programming problems Back to roadmap