#213
House Robber II
Medium 1D DP on two ranges
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Same as House Robber, but the houses form a circle, so the first and last are adjacent.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: same, but the houses are in a circle.
Why this works: the first and last can't both be robbed, so solve without the last, solve without the first, and take the better.
Example: [2, 3, 2]
without last [2, 3] → 3without first [3, 2] → 3 → answer 3
✦Hints open one at a time
You can't take both the first and the last house.
Solve the straight-line problem twice: without the last house, and without the first. Take the better.
↗Approach
Reuse the linear robber on [0, n − 2] and [1, n − 1]. Handle n = 1 separately.
</>Solution (Java)
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1)); // drop last or first
}
private int robLine(int[] nums, int lo, int hi) {
int prev2 = 0, prev1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}!Common mistake
Forgetting n = 1, where both ranges are empty and the answer is nums[0].
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon