House Robber II
Houses form a circle, so the first and last houses are neighbors. Choose nonadjacent houses to maximize the total money.
Work through the cases
3 examplesInput notation
Nonnegative house values separated by spaces.Expected result
The maximum total.Case 1
Input
2 3 2
Expected output
3
Case 2
Input
1 2 3 1
Expected output
4
Case 3
Input
7
Expected output
7
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Houses form a circle, so the first and last cannot both be robbed, and the linear recurrence does not apply directly. We split into two linear instances—drop the first house, or drop the last—and take the better of the two. A single house is returned as-is.
The circular arrangement means that at most one of the first and last houses can be chosen for theft, so this circular arrangement problem can be reduced to two single-row house problems.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private int rob(int[] nums, int l, int r) {
int f = 0, g = 0;
for (; l <= r; ++l) {
int ff = Math.max(f, g);
g = f + nums[l];
f = ff;
}
return Math.max(f, g);
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.