House Robber II
The briefingthe full drill, in my own words
The drill: The same street of houses, but now it loops into a circle — the first and last house are neighbors too. Maximize the non-adjacent haul under that wraparound rule.
The same row of houses returns, but now the street bends into a circle — the first house and the last house count as neighbors too, on top of every ordinary adjacent pair.
The same no-two-adjacent rule applies under that wraparound: robbing both the first and the last house at once is exactly as forbidden as robbing any other neighboring pair.
The task is still a single maximum total haul, now respecting the circular constraint instead of the straight one.
- house count can run into the low thousands
- each house's haul is a non-negative integer
- first and last houses count as adjacent in addition to normal neighbors
- answer is the maximum total haul under that circular rule
The hintstake only what you need
HINT 1 THE NUDGE
The circle adds exactly one new constraint over a straight street: the first and last house can't both be robbed. What does that split the problem into?
HINT 2 THE STRUCTURE
Either the first house is off the table, or the last house is — run the ordinary street version on both cuts of the circle and see which cut wins.
HINT 3 ONE STEP FROM THE ANSWER
Solve the linear house-robber on nums[0..n-2] and again on nums[1..n-1], then take the larger of the two totals — the wraparound is handled entirely by which end you drop.
Coach's boardthe pattern, step by step
The street bends into a circle — house 0 and house 2 count as neighbors too, so both can't be robbed.
The splitstwo paces, two languages
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
def line(row: List[int]) -> int: # O(1)-space rolling DP
prev2, prev1 = 0, 0
for x in row:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
return max(line(nums[:-1]), line(nums[1:]))class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
def line(row: List[int]) -> int: # plain house-robber recursion, no memo
n = len(row)
def best(i: int) -> int:
if i >= n:
return 0
return max(best(i + 1), row[i] + best(i + 2))
return best(0)
return max(line(nums[:-1]), line(nums[1:])) # drop the last house, or the firstclass Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(line(nums, 0, n - 1), line(nums, 1, n));
}
// rolling O(1)-space DP over nums[from, to)
private int line(int[] nums, int from, int to) {
int prev2 = 0, prev1 = 0;
for (int i = from; i < to; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(line(nums, 0, n - 1), line(nums, 1, n));
}
// plain house-robber recursion, no memo, over nums[from, to)
private int line(int[] nums, int from, int to) {
return best(nums, from, to);
}
private int best(int[] nums, int i, int to) {
if (i >= to) {
return 0;
}
return Math.max(best(nums, i + 1, to), nums[i] + best(nums, i + 2, to));
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED