MediumNeetCode150ArrayDynamic Programming
House Robber II
Circular houses, cannot rob adjacent.
Examples
Input
nums = [1,2,3,1]
Output
3
Circular means first and last adjacent.
Constraints
- •
1 <= nums.length <= 100 - •
0 <= nums[i] <= 400
Approaches
Include/exclude, circular.
CodeT: O(2^n) | S: O(n) stack
Check [0..n-2] and [1..n-1].
CodeT: O(n) | S: O(n)
Same as house robber for two ranges.
CodeT: O(n) | S: O(1)
def rob(nums):
def h(nums):
if len(nums)==1: return nums[0]
a,b=max(nums[0],nums[1]),nums[0]
for i in range(2,len(nums)): a,b=max(a,b+nums[i]),a
return a
return max(h(nums[:-1]),h(nums[1:])) if len(nums)>1 else nums[0]Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^n) | O(n) stack | Include/exclude, circular. |
| DP Two Ranges | O(n) | O(n) | Check [0..n-2] and [1..n-1]. |
| DP Optimized | O(n) | O(1) | Same as house robber for two ranges. |
Recursion
T: O(2^n)S: O(n) stack
Include/exclude, circular.
DP Two Ranges
T: O(n)S: O(n)
Check [0..n-2] and [1..n-1].
DP Optimized
T: O(n)S: O(1)
Same as house robber for two ranges.
Common Mistakes
Not handling circular properly
Double counting
Single house edge case