DSA-129 · FOCUSED PRACTICE
House Robber II
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 9864 deterministic checks. Learner drafts are not executed.
Understand the problem
nums[i] is the nonnegative money in house i on a circular street. Consecutive indices are neighbors, and for at least two houses the last and first houses are also neighbors. Choose a subset containing no neighboring pair and return its maximum total money.
- nums must be non-null with at most 100,000 nonnegative int entries; Integer.MAX_VALUE is allowed. Null throws NullPointerException, and excessive length or any negative value throws IllegalArgumentException. Validate the complete source before handling short inputs.
- Return an exact long value and preserve nums. Choosing no houses is legal. An empty street returns 0. A one-house street returns that house value: the single house is selectable and is not treated as its own forbidden neighbor.
- For n≥2, indices 0 and n−1 cannot both be selected. For n=2 this is simply the same neighboring pair as consecutive adjacency. Only a maximum value is requested; no witness or tie preference is returned. The recursive baseline enumerates only small inputs in tests.
Examples
Input:
nums=[2,3,2]
Output:3The two endpoint 2s are neighbors on the circle. The linear answer 4 is invalid here.
Input:
nums=[1,2,3,1]
Output:4Take indices 0 and 2. The case excluding the last house achieves 4; excluding the first achieves 3.
Input:
nums=[10,1,1,10]
Output:11The linear endpoint total 20 is forbidden; choose one endpoint and the nonadjacent interior house.
Input:
nums=[7]
Output:7The explicit singleton convention avoids excluding the only house in both range cases.
Before you start
- House Robber on a half-open linear range
- Exhaustive case coverage versus disjoint counting cases
Recognize the structure
The linear DP handles neighboring indices but cannot forget whether the first house was chosen when it reaches the last. Rather than add a history bit to every state, split the feasible solutions into cases that exclude an endpoint. Removing either endpoint cuts the circle into a path and permits the existing linear recurrence. This illustrates a general technique: isolate the small piece of long-range dependency before compressing state.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 117/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
What single pair of indices makes the circular version differ from the linear one?
Hint 2
Every feasible solution excludes at least one endpoint. Can each exclusion leave a path?
Hint 3
Handle n≤1 explicitly, then return max(rob range [0,n−1), rob range [1,n)) with fresh rolling registers.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate subsets while remembering the first choice
The suffix recursion carries index and firstTaken. Skip advances one index; take adds the current value and advances two. At the last house of a street with more than one house, taking is forbidden if the first was taken. The singleton is exempt from that final check. This explicitly models the wraparound dependency instead of splitting ranges. It has O(2^n) upper-bound time and O(n+1) stack space. Its results are checked against independent bit masks that reject both adjacent bits and the endpoint pair. Only small arrays run the baseline; the production reference is iterative.
Improve the baseline
Find the missing dependency in the linear state
A two-register prefix optimum remembers the best amount but not whether its subset contains house 0. On a path that omission is safe; on a circle the final house needs that fact. Applying House Robber directly to the whole array can return an infeasible value, such as 4 for [2,3,2].
Cover every solution with endpoint exclusions
For n≥2, no valid subset contains both endpoints. Therefore every valid subset excludes the last, excludes the first, or excludes both. Let A be the path optimum on indices [0,n−1) and B the path optimum on [1,n). The circular answer is max(A,B). These cases overlap, but overlap is harmless when taking a maximum; it would matter when counting subsets.
Reuse a half-open range helper
range(nums,start,end) considers original indices start through end−1 with no array slicing. Both rolling values reset to zero on every call; the initial compatible prefix is empty relative to that range. For each index compute take from the two-back optimum, skip from the one-back optimum, and delay the shift until next is known.
Handle zero and one before range splitting
For n=0 return 0; for n=1 return nums[0]. Splitting a singleton into [0,0) and [1,1) would produce two empty ranges and incorrectly return zero. For n=2 the ranges each contain one endpoint, yielding the larger value as required. Complete validation still precedes these cases.
Keep the cases separate until the final comparison
For [10,1,1,10], excluding the last gives 11 and excluding the first gives 11. Adding these values would combine incompatible solutions; taking their maximum selects an achievable case optimum. Each pass uses its own fresh frontier. Because money is nonnegative and length is bounded, even a loose sum of all entries fits long; no int sum is used.
Why it is correct
Special sizes
An empty set is optimal on an empty street. A singleton has no distinct neighbor and can be chosen, giving its nonnegative value. For n≥2 the two endpoint exclusions each produce a nonempty or ordinary path with well-defined half-open bounds.
Case soundness and coverage
Every subset produced in [0,n−1) omits the last endpoint, so path adjacency checks also imply circular feasibility. The same holds for [1,n), which omits the first. Conversely any circular feasible subset must omit at least one endpoint and thus belongs to one or both ranges. The greater range optimum is therefore both achievable and at least as large as every circular feasible total.
Helper induction and finite evaluation
Within each range, taking index i excludes its predecessor and uses the two-back prefix optimum; skipping uses the one-back optimum. Their maximum is exact by the path include/exclude proof. Fresh zero registers establish the base for either start value. Each index advances toward end, each range returns its optimum, and the final Math.max returns the circular optimum without modifying any source entry.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Objects;
public final class Solution {
private Solution() {}
private static void validate(int[] nums) {
Objects.requireNonNull(nums, "nums");
if (nums.length > 100_000) throw new IllegalArgumentException("too many houses");
for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money");
}
public static long rob(int[] nums) {
validate(nums);
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
long withoutLast = range(nums, 0, nums.length - 1);
long withoutFirst = range(nums, 1, nums.length);
return Math.max(withoutLast, withoutFirst);
}
private static long range(int[] nums, int start, int end) {
long previousTwo = 0, previousOne = 0;
for (int index = start; index < end; index++) {
long take = previousTwo + nums[index];
long skip = previousOne;
long next = Math.max(skip, take);
previousTwo = previousOne;
previousOne = next;
}
return previousOne;
}
// Baseline: enumerate choices while remembering whether house 0 was taken.
public static long baseline(int[] nums) {
validate(nums);
return enumerate(nums, 0, false);
}
private static long enumerate(int[] nums, int index, boolean firstTaken) {
if (index >= nums.length) return 0;
long skip = enumerate(nums, index + 1, firstTaken);
if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip;
long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0);
return Math.max(skip, take);
}
}
Read the meaningful blocks
Validate before special-size returns
Checking the entire nonnegative source prevents a singleton negative input from bypassing the contract. The n=1 branch records an intentional problem definition, not an arbitrary implementation shortcut.
Call both ranges with original indices
withoutLast uses start 0, end n−1, excluding index n−1. withoutFirst uses start 1, end n, excluding index 0. Half-open boundaries avoid array copies and make n=2 easy to inspect. The helper does not independently revalidate an already validated array.
Reset and combine correctly
Each helper call allocates fresh scalar locals initialized to zero. The final maximum chooses between feasible case totals. Registers cannot carry from the first call into the second, and range totals must never be added.
Complexity
Complete validation plus two passes over n−1 houses costs O(n+1) time. Each pass uses a fixed number of long registers, and no slices or tables are allocated: O(1) auxiliary storage. Output is one exact long.
The history-aware recursive baseline has O(2^n) upper-bound time and O(n+1) stack space. A solution with a first-taken state bit can also run in O(n) time and constant frontier space, but needs careful incompatible-state sentinels. Two path calls give a smaller proof surface for the value-only API.
Exact-state walkthroughs
Reveal normal and boundary traces
Circular endpoints cannot combine
Input: [2,3,2] · Maximum circular nonadjacent total: 3
Step 1 of 15: Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
Phase: validated.
B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])
The complete input satisfies the documented contract. The next step establishes base states before any transition.
Original house indices and money — index identity determines adjacency.
- 0: 2available in this pass
- 1: 3available in this pass
- 2: 2available in this pass
Indices 0 and 2 are neighbors. A pass excludes one endpoint; it never forces the other endpoint to be selected.
Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.
| Variable | Value |
|---|---|
| input | [2,3,2] |
| phase | "validated" |
| caseResults | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] nums) { 6 Objects.requireNonNull(nums, "nums"); 7 if (nums.length > 100_000) throw new IllegalArgumentException("too many houses"); 8 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money"); 9 } 10 public static long rob(int[] nums) { 11 validate(nums); 12 if (nums.length == 0) return 0; 13 if (nums.length == 1) return nums[0]; 14 long withoutLast = range(nums, 0, nums.length - 1); 15 long withoutFirst = range(nums, 1, nums.length); 16 return Math.max(withoutLast, withoutFirst); 17 } 18 private static long range(int[] nums, int start, int end) { 19 long previousTwo = 0, previousOne = 0; 20 for (int index = start; index < end; index++) { 21 long take = previousTwo + nums[index]; 22 long skip = previousOne; 23 long next = Math.max(skip, take); 24 previousTwo = previousOne; 25 previousOne = next; 26 } 27 return previousOne; 28 } 29 // Baseline: enumerate choices while remembering whether house 0 was taken. 30 public static long baseline(int[] nums) { 31 validate(nums); 32 return enumerate(nums, 0, false); 33 } 34 private static long enumerate(int[] nums, int index, boolean firstTaken) { 35 if (index >= nums.length) return 0; 36 long skip = enumerate(nums, index + 1, firstTaken); 37 if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip; 38 long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0); 39 return Math.max(skip, take); 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
- input
[2,3,2]- phase
"validated"- caseResults
[]
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[2,3,2]- phase
"range-start"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
-1
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2,3,2]- phase
"candidate"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
0- two
2- one
0- next
2
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2,3,2]- phase
"commit"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,2,null]- previousTwo
0- previousOne
2- position
0- two
2- one
0- next
2
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2,3,2]- phase
"candidate"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,2,null]- previousTwo
0- previousOne
2- position
1- two
3- one
2- next
3
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2,3,2]- phase
"commit"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,2,3]- previousTwo
2- previousOne
3- position
1- two
3- one
2- next
3
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[2,3,2]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3}]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,2,3]- previousTwo
2- previousOne
3- position
1- answer
3
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[2,3,2]- phase
"range-start"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
0
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2,3,2]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
1- two
3- one
0- next
3
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2,3,2]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,3,null]- previousTwo
0- previousOne
3- position
1- two
3- one
0- next
3
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2,3,2]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,3,null]- previousTwo
0- previousOne
3- position
2- two
2- one
3- next
3
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2,3,2]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,3,3]- previousTwo
3- previousOne
3- position
2- two
2- one
3- next
3
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[2,3,2]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3},{"caseLabel":"Exclude first house","start":1,"end":3,"value":3}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,3,3]- previousTwo
3- previousOne
3- position
2- answer
3
- Choose the larger endpoint-excluding path optimum.
Every circular feasible subset excludes at least one endpoint. Both cases are feasible and may overlap. A maximum tolerates overlap; adding case values or counts would require different reasoning.
- input
[2,3,2]- phase
"combine"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":3},{"caseLabel":"Exclude first house","start":1,"end":3,"value":3}]- answer
3
- Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
- result
3
Empty circle
Input: [] · Maximum circular nonadjacent total: 0
Step 1 of 3: Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
Phase: validated.
B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])
The complete input satisfies the documented contract. The next step establishes base states before any transition.
Original house indices and money — index identity determines adjacency.
No entries.
Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.
| Variable | Value |
|---|---|
| input | [] |
| phase | "validated" |
| caseResults | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] nums) { 6 Objects.requireNonNull(nums, "nums"); 7 if (nums.length > 100_000) throw new IllegalArgumentException("too many houses"); 8 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money"); 9 } 10 public static long rob(int[] nums) { 11 validate(nums); 12 if (nums.length == 0) return 0; 13 if (nums.length == 1) return nums[0]; 14 long withoutLast = range(nums, 0, nums.length - 1); 15 long withoutFirst = range(nums, 1, nums.length); 16 return Math.max(withoutLast, withoutFirst); 17 } 18 private static long range(int[] nums, int start, int end) { 19 long previousTwo = 0, previousOne = 0; 20 for (int index = start; index < end; index++) { 21 long take = previousTwo + nums[index]; 22 long skip = previousOne; 23 long next = Math.max(skip, take); 24 previousTwo = previousOne; 25 previousOne = next; 26 } 27 return previousOne; 28 } 29 // Baseline: enumerate choices while remembering whether house 0 was taken. 30 public static long baseline(int[] nums) { 31 validate(nums); 32 return enumerate(nums, 0, false); 33 } 34 private static long enumerate(int[] nums, int index, boolean firstTaken) { 35 if (index >= nums.length) return 0; 36 long skip = enumerate(nums, index + 1, firstTaken); 37 if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip; 38 long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0); 39 return Math.max(skip, take); 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
- input
[]- phase
"validated"- caseResults
[]
- An empty circle permits only the empty selection.
Do not split a singleton into two empty endpoint-exclusion ranges. Full validation has already happened.
- input
[]- phase
"base"- caseResults
[]- answer
0
- Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
- result
0
Singleton has no distinct neighbor
Input: [7] · Maximum circular nonadjacent total: 7
Step 1 of 3: Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
Phase: validated.
B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])
The complete input satisfies the documented contract. The next step establishes base states before any transition.
Original house indices and money — index identity determines adjacency.
- 0: 7available in this pass
Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.
| Variable | Value |
|---|---|
| input | [7] |
| phase | "validated" |
| caseResults | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] nums) { 6 Objects.requireNonNull(nums, "nums"); 7 if (nums.length > 100_000) throw new IllegalArgumentException("too many houses"); 8 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money"); 9 } 10 public static long rob(int[] nums) { 11 validate(nums); 12 if (nums.length == 0) return 0; 13 if (nums.length == 1) return nums[0]; 14 long withoutLast = range(nums, 0, nums.length - 1); 15 long withoutFirst = range(nums, 1, nums.length); 16 return Math.max(withoutLast, withoutFirst); 17 } 18 private static long range(int[] nums, int start, int end) { 19 long previousTwo = 0, previousOne = 0; 20 for (int index = start; index < end; index++) { 21 long take = previousTwo + nums[index]; 22 long skip = previousOne; 23 long next = Math.max(skip, take); 24 previousTwo = previousOne; 25 previousOne = next; 26 } 27 return previousOne; 28 } 29 // Baseline: enumerate choices while remembering whether house 0 was taken. 30 public static long baseline(int[] nums) { 31 validate(nums); 32 return enumerate(nums, 0, false); 33 } 34 private static long enumerate(int[] nums, int index, boolean firstTaken) { 35 if (index >= nums.length) return 0; 36 long skip = enumerate(nums, index + 1, firstTaken); 37 if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip; 38 long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0); 39 return Math.max(skip, take); 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
- input
[7]- phase
"validated"- caseResults
[]
- A singleton has no distinct neighboring house.
Do not split a singleton into two empty endpoint-exclusion ranges. Full validation has already happened.
- input
[7]- phase
"base"- caseResults
[]- answer
7
- Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
- result
7
Neither endpoint must be chosen
Input: [1,10,1] · Maximum circular nonadjacent total: 10
Step 1 of 15: Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
Phase: validated.
B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])
The complete input satisfies the documented contract. The next step establishes base states before any transition.
Original house indices and money — index identity determines adjacency.
- 0: 1available in this pass
- 1: 10available in this pass
- 2: 1available in this pass
Indices 0 and 2 are neighbors. A pass excludes one endpoint; it never forces the other endpoint to be selected.
Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.
| Variable | Value |
|---|---|
| input | [1,10,1] |
| phase | "validated" |
| caseResults | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] nums) { 6 Objects.requireNonNull(nums, "nums"); 7 if (nums.length > 100_000) throw new IllegalArgumentException("too many houses"); 8 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money"); 9 } 10 public static long rob(int[] nums) { 11 validate(nums); 12 if (nums.length == 0) return 0; 13 if (nums.length == 1) return nums[0]; 14 long withoutLast = range(nums, 0, nums.length - 1); 15 long withoutFirst = range(nums, 1, nums.length); 16 return Math.max(withoutLast, withoutFirst); 17 } 18 private static long range(int[] nums, int start, int end) { 19 long previousTwo = 0, previousOne = 0; 20 for (int index = start; index < end; index++) { 21 long take = previousTwo + nums[index]; 22 long skip = previousOne; 23 long next = Math.max(skip, take); 24 previousTwo = previousOne; 25 previousOne = next; 26 } 27 return previousOne; 28 } 29 // Baseline: enumerate choices while remembering whether house 0 was taken. 30 public static long baseline(int[] nums) { 31 validate(nums); 32 return enumerate(nums, 0, false); 33 } 34 private static long enumerate(int[] nums, int index, boolean firstTaken) { 35 if (index >= nums.length) return 0; 36 long skip = enumerate(nums, index + 1, firstTaken); 37 if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip; 38 long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0); 39 return Math.max(skip, take); 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
- input
[1,10,1]- phase
"validated"- caseResults
[]
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[1,10,1]- phase
"range-start"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
-1
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[1,10,1]- phase
"candidate"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
0- two
1- one
0- next
1
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[1,10,1]- phase
"commit"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,1,null]- previousTwo
0- previousOne
1- position
0- two
1- one
0- next
1
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[1,10,1]- phase
"candidate"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,1,null]- previousTwo
0- previousOne
1- position
1- two
10- one
1- next
10
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[1,10,1]- phase
"commit"- caseResults
[]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,1,10]- previousTwo
1- previousOne
10- position
1- two
10- one
1- next
10
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[1,10,1]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10}]- start
0- end
2- caseLabel
"Exclude last house"- table
[0,1,10]- previousTwo
1- previousOne
10- position
1- answer
10
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[1,10,1]- phase
"range-start"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
0
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[1,10,1]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,null,null]- previousTwo
0- previousOne
0- position
1- two
10- one
0- next
10
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[1,10,1]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,10,null]- previousTwo
0- previousOne
10- position
1- two
10- one
0- next
10
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[1,10,1]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,10,null]- previousTwo
0- previousOne
10- position
2- two
1- one
10- next
10
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[1,10,1]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,10,10]- previousTwo
10- previousOne
10- position
2- two
1- one
10- next
10
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[1,10,1]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10},{"caseLabel":"Exclude first house","start":1,"end":3,"value":10}]- start
1- end
3- caseLabel
"Exclude first house"- table
[0,10,10]- previousTwo
10- previousOne
10- position
2- answer
10
- Choose the larger endpoint-excluding path optimum.
Every circular feasible subset excludes at least one endpoint. Both cases are feasible and may overlap. A maximum tolerates overlap; adding case values or counts would require different reasoning.
- input
[1,10,1]- phase
"combine"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":2,"value":10},{"caseLabel":"Exclude first house","start":1,"end":3,"value":10}]- answer
10
- Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
- result
10
Two neighboring houses
Input: [5,9] · Maximum circular nonadjacent total: 9
Step 1 of 11: Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
Phase: validated.
B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])
The complete input satisfies the documented contract. The next step establishes base states before any transition.
Original house indices and money — index identity determines adjacency.
- 0: 5available in this pass
- 1: 9available in this pass
Indices 0 and 1 are neighbors. A pass excludes one endpoint; it never forces the other endpoint to be selected.
Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.
| Variable | Value |
|---|---|
| input | [5,9] |
| phase | "validated" |
| caseResults | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] nums) { 6 Objects.requireNonNull(nums, "nums"); 7 if (nums.length > 100_000) throw new IllegalArgumentException("too many houses"); 8 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money"); 9 } 10 public static long rob(int[] nums) { 11 validate(nums); 12 if (nums.length == 0) return 0; 13 if (nums.length == 1) return nums[0]; 14 long withoutLast = range(nums, 0, nums.length - 1); 15 long withoutFirst = range(nums, 1, nums.length); 16 return Math.max(withoutLast, withoutFirst); 17 } 18 private static long range(int[] nums, int start, int end) { 19 long previousTwo = 0, previousOne = 0; 20 for (int index = start; index < end; index++) { 21 long take = previousTwo + nums[index]; 22 long skip = previousOne; 23 long next = Math.max(skip, take); 24 previousTwo = previousOne; 25 previousOne = next; 26 } 27 return previousOne; 28 } 29 // Baseline: enumerate choices while remembering whether house 0 was taken. 30 public static long baseline(int[] nums) { 31 validate(nums); 32 return enumerate(nums, 0, false); 33 } 34 private static long enumerate(int[] nums, int index, boolean firstTaken) { 35 if (index >= nums.length) return 0; 36 long skip = enumerate(nums, index + 1, firstTaken); 37 if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip; 38 long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0); 39 return Math.max(skip, take); 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
- input
[5,9]- phase
"validated"- caseResults
[]
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[5,9]- phase
"range-start"- caseResults
[]- start
0- end
1- caseLabel
"Exclude last house"- table
[0,null]- previousTwo
0- previousOne
0- position
-1
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[5,9]- phase
"candidate"- caseResults
[]- start
0- end
1- caseLabel
"Exclude last house"- table
[0,null]- previousTwo
0- previousOne
0- position
0- two
5- one
0- next
5
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[5,9]- phase
"commit"- caseResults
[]- start
0- end
1- caseLabel
"Exclude last house"- table
[0,5]- previousTwo
0- previousOne
5- position
0- two
5- one
0- next
5
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[5,9]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":1,"value":5}]- start
0- end
1- caseLabel
"Exclude last house"- table
[0,5]- previousTwo
0- previousOne
5- position
0- answer
5
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[5,9]- phase
"range-start"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":1,"value":5}]- start
1- end
2- caseLabel
"Exclude first house"- table
[0,null]- previousTwo
0- previousOne
0- position
0
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[5,9]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":1,"value":5}]- start
1- end
2- caseLabel
"Exclude first house"- table
[0,null]- previousTwo
0- previousOne
0- position
1- two
9- one
0- next
9
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[5,9]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":1,"value":5}]- start
1- end
2- caseLabel
"Exclude first house"- table
[0,9]- previousTwo
0- previousOne
9- position
1- two
9- one
0- next
9
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[5,9]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":1,"value":5},{"caseLabel":"Exclude first house","start":1,"end":2,"value":9}]- start
1- end
2- caseLabel
"Exclude first house"- table
[0,9]- previousTwo
0- previousOne
9- position
1- answer
9
- Choose the larger endpoint-excluding path optimum.
Every circular feasible subset excludes at least one endpoint. Both cases are feasible and may overlap. A maximum tolerates overlap; adding case values or counts would require different reasoning.
- input
[5,9]- phase
"combine"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":1,"value":5},{"caseLabel":"Exclude first house","start":1,"end":2,"value":9}]- answer
9
- Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
- result
9
Long total on a four-cycle
Input: [2147483647,0,2147483647,0] · Maximum circular nonadjacent total: 4294967294
Step 1 of 19: Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
Phase: validated.
B(k+1) = max(B(k), B(max(0,k−1)) + nums[index])
The complete input satisfies the documented contract. The next step establishes base states before any transition.
Original house indices and money — index identity determines adjacency.
- 0: 2147483647available in this pass
- 1: 0available in this pass
- 2: 2147483647available in this pass
- 3: 0available in this pass
Indices 0 and 3 are neighbors. A pass excludes one endpoint; it never forces the other endpoint to be selected.
Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.
| Variable | Value |
|---|---|
| input | [2147483647,0,2147483647,0] |
| phase | "validated" |
| caseResults | [] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] nums) { 6 Objects.requireNonNull(nums, "nums"); 7 if (nums.length > 100_000) throw new IllegalArgumentException("too many houses"); 8 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative money"); 9 } 10 public static long rob(int[] nums) { 11 validate(nums); 12 if (nums.length == 0) return 0; 13 if (nums.length == 1) return nums[0]; 14 long withoutLast = range(nums, 0, nums.length - 1); 15 long withoutFirst = range(nums, 1, nums.length); 16 return Math.max(withoutLast, withoutFirst); 17 } 18 private static long range(int[] nums, int start, int end) { 19 long previousTwo = 0, previousOne = 0; 20 for (int index = start; index < end; index++) { 21 long take = previousTwo + nums[index]; 22 long skip = previousOne; 23 long next = Math.max(skip, take); 24 previousTwo = previousOne; 25 previousOne = next; 26 } 27 return previousOne; 28 } 29 // Baseline: enumerate choices while remembering whether house 0 was taken. 30 public static long baseline(int[] nums) { 31 validate(nums); 32 return enumerate(nums, 0, false); 33 } 34 private static long enumerate(int[] nums, int index, boolean firstTaken) { 35 if (index >= nums.length) return 0; 36 long skip = enumerate(nums, index + 1, firstTaken); 37 if (nums.length > 1 && index == nums.length - 1 && firstTaken) return skip; 38 long take = (long) nums[index] + enumerate(nums, index + 2, firstTaken || index == 0); 39 return Math.max(skip, take); 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
- input
[2147483647,0,2147483647,0]- phase
"validated"- caseResults
[]
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[2147483647,0,2147483647,0]- phase
"range-start"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,null,null,null]- previousTwo
0- previousOne
0- position
-1
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2147483647,0,2147483647,0]- phase
"candidate"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,null,null,null]- previousTwo
0- previousOne
0- position
0- two
2147483647- one
0- next
2147483647
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2147483647,0,2147483647,0]- phase
"commit"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,2147483647,null,null]- previousTwo
0- previousOne
2147483647- position
0- two
2147483647- one
0- next
2147483647
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2147483647,0,2147483647,0]- phase
"candidate"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,2147483647,null,null]- previousTwo
0- previousOne
2147483647- position
1- two
0- one
2147483647- next
2147483647
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2147483647,0,2147483647,0]- phase
"commit"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,2147483647,2147483647,null]- previousTwo
2147483647- previousOne
2147483647- position
1- two
0- one
2147483647- next
2147483647
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2147483647,0,2147483647,0]- phase
"candidate"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,2147483647,2147483647,null]- previousTwo
2147483647- previousOne
2147483647- position
2- two
4294967294- one
2147483647- next
4294967294
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2147483647,0,2147483647,0]- phase
"commit"- caseResults
[]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,2147483647,2147483647,4294967294]- previousTwo
2147483647- previousOne
4294967294- position
2- two
4294967294- one
2147483647- next
4294967294
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[2147483647,0,2147483647,0]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
0- end
3- caseLabel
"Exclude last house"- table
[0,2147483647,2147483647,4294967294]- previousTwo
2147483647- previousOne
4294967294- position
2- answer
4294967294
- Reset an empty prefix for this half-open path range.
Only original indices start..end−1 belong to this pass. Prefix length zero has optimum zero. Both registers reset independently of all earlier passes.
- input
[2147483647,0,2147483647,0]- phase
"range-start"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,null,null,null]- previousTwo
0- previousOne
0- position
0
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2147483647,0,2147483647,0]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,null,null,null]- previousTwo
0- previousOne
0- position
1- two
0- one
0- next
0
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2147483647,0,2147483647,0]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,0,null,null]- previousTwo
0- previousOne
0- position
1- two
0- one
0- next
0
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2147483647,0,2147483647,0]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,0,null,null]- previousTwo
0- previousOne
0- position
2- two
2147483647- one
0- next
2147483647
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2147483647,0,2147483647,0]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,0,2147483647,null]- previousTwo
0- previousOne
2147483647- position
2- two
2147483647- one
0- next
2147483647
- Compare taking this house with skipping it.
take uses the two-back prefix and this house; skip uses the one-back prefix. A prefix optimum need not include its last house. Both candidates use the old pair.
- input
[2147483647,0,2147483647,0]- phase
"candidate"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,0,2147483647,null]- previousTwo
0- previousOne
2147483647- position
3- two
0- one
2147483647- next
2147483647
- Commit the best prefix before advancing to the next house.
The two live registers now describe the previous and current prefix lengths relative to this range. The full table shown here is explanatory history; Java uses constant workspace.
- input
[2147483647,0,2147483647,0]- phase
"commit"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,0,2147483647,2147483647]- previousTwo
2147483647- previousOne
2147483647- position
3- two
0- one
2147483647- next
2147483647
- Finish this complete path range.
The pass has evaluated every house in its range. Its scalar optimum is feasible on that path; source indices and values remain unchanged.
- input
[2147483647,0,2147483647,0]- phase
"range-complete"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294},{"caseLabel":"Exclude first house","start":1,"end":4,"value":2147483647}]- start
1- end
4- caseLabel
"Exclude first house"- table
[0,0,2147483647,2147483647]- previousTwo
2147483647- previousOne
2147483647- position
3- answer
2147483647
- Choose the larger endpoint-excluding path optimum.
Every circular feasible subset excludes at least one endpoint. Both cases are feasible and may overlap. A maximum tolerates overlap; adding case values or counts would require different reasoning.
- input
[2147483647,0,2147483647,0]- phase
"combine"- caseResults
[{"caseLabel":"Exclude last house","start":0,"end":3,"value":4294967294},{"caseLabel":"Exclude first house","start":1,"end":4,"value":2147483647}]- answer
4294967294
- Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
- result
4294967294
Test the contract
Input:
nums=[]
Output:0Empty-circle convention.
Input:
nums=[5,9]
Output:9The two distinct houses are neighbors.
Input:
nums=[1,10,1]
Output:10Neither endpoint needs to be selected.
Input:
nums=[0,0,0]
Output:0Overlapping zero-optimum cases are fine for max.
Input:
nums=[2147483647,0,2147483647,0]
Output:4294967294Nonadjacent houses 0 and 2 are compatible on a four-cycle.
Input:
nums=[-1]
Output:IllegalArgumentExceptionValidation precedes singleton handling.
Common mistakes and counterexamples
Use linear robbery on all houses
Counterexample: [2,3,2] would return the infeasible endpoint sum 4.
Exclude one endpoint per path case before using the linear recurrence.
Force first or last to be selected
Counterexample: [1,10,1] has optimum 10, selecting neither endpoint.
Cases exclude an endpoint; they do not require selecting the opposite endpoint.
Add the two path optima
Counterexample: [10,1,1,10] gives 11 in both cases, but 22 is not a valid circular value.
Take the maximum. Overlapping feasible families cover alternatives rather than independent subproblems to combine.
Forget singleton or half-open bounds
Counterexample: [7] becomes zero if both ranges are empty; including end accidentally restores the circle.
Return a singleton directly and specify [start,end) for every helper call.
Follow-ups
Recover one circular optimal subset.
Compare the two path optima and select a case using an explicit tie policy. Run or retain a full prefix table for that range, then reconstruct original indices. Verify both consecutive adjacency and the wraparound pair. Computing both scalar optima remains constant space, but storing a witness is a separate cost.
Count all distinct optimal subsets on the circle.
The endpoint-exclusion families overlap on subsets omitting both endpoints, so adding their optimum counts double-counts an intersection when values tie. A cleaner counting split uses mutually exclusive cases: first house chosen versus first house excluded. Enforce forbidden neighbors and carry value/count pairs with an explicit large-integer policy.
Move from a cycle to a tree or a general graph.
On a rooted tree maintain include/exclude values for each subtree: including a vertex forces every child excluded, while exclusion permits each child optimum. Use iterative postorder for deep trees. On a general graph this becomes maximum-weight independent set and the path/cycle recurrence does not extend to an arbitrary polynomial-time DP without additional structure.