Houses in a circle · the last house is next door to house 0
run 1 · skipFirst house 0 left out · best from house 1 to j
run 2 · skipLast last house left out · best from house 0 to j
public int rob(int[] nums) { int n = nums.length; int skipFirst = helper(Arrays.copyOfRange(nums, 1, n)); int skipLast = helper(Arrays.copyOfRange(nums, 0, n - 1)); return Math.max(nums[0], Math.max(skipFirst, skipLast));}private int helper(int[] nums) { // House Robber I int rob1 = 0; int rob2 = 0; for (int n : nums) { int newRob = Math.max(rob1 + n, rob2); rob1 = rob2; rob2 = newRob; } return rob2;}
- run
- —
- n
- —
- rob1
- —
- rob2
- —
- results
- —
Why it works
- Brute force tries every set of houses with no two neighbours, now also checking that house 0 and the last house are not both taken: exponential.
- Break the circle: the first and last house can never both be robbed. So the answer leaves out house 0 or leaves out the last house (or both). Each case is a straight street, which House Robber I solves. Take the larger of the two runs.
- Two linear passes: each run is the House Robber I loop with two variables, so O(n) time. The copies
Arrays.copyOfRange(nums, 1, n)andArrays.copyOfRange(nums, 0, n - 1)take O(n) space; pass index bounds instead and the space drops to O(1). - Pitfall: one house. Both copies are empty and both runs return 0, so the answer must also consider
nums[0]. That is why the first argument ofmaxis there. - Invariant per run:
rob2is the best from the houses seen so far in that run,rob1the best without the last one. Watch the rob arc reach back two cells and the skip arc one cell. - Related: House Robber III puts the houses on a binary tree and returns a rob/skip pair per node.