Pattern visualizer
House Robber II
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. Animated on: nums = [2, 3, 2] — houses arranged in a circle. Maximize loot without robbing adjacent houses..
Circular DP via two linear House Robber passes
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).
1FUNCTION rob(nums):2 IF the length of nums is 1: RETURN nums[0]3 FUNCTION robLinear(arr):4 prev2 = 0, prev1 = 05 FOR each x in arr:6 cur = the larger of prev1 and prev2 + x7 prev2 = prev1; prev1 = cur8 RETURN prev19 RETURN the larger of robLinear(nums[0..n-2]) and robLinear(nums[1..n-1])
← / → step · space play · Home restart