House Robber II
Medium1-D dynamic programming
Houses stand in a circle, so the first house and the last house are next to each other. nums[i] is the cash in house i. A thief can take the cash from any houses he likes, but never from two neighbouring houses: that sets off the alarm.
Return the most cash he can take.
Examples
Input: nums = [4, 2, 5] Output: 5
In a circle of three, every house is next to the other two, so only one can be taken.
Input: nums = [3, 6, 2, 8] Output: 14
Take 6 and 8: they are not neighbours, even in the circle.
Constraints
1 ≤ nums.length ≤ 1000 ≤ nums[i] ≤ 1000
Stuck?
Hint 1
The circle only adds one rule: the first and the last house cannot both be taken. So at least one of them is left out.
Hint 2
Solve the straight row twice, once without the last house and once without the first, and return the larger total. Watch out for a single house.
The idea
The circle adds a single rule to the straight row: the first and the last house cannot both be taken. So every allowed plan leaves out the first house or the last one. Solve the row without the first house and the row without the last, and the larger total covers every plan.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
A single house has no neighbour, so the thief takes it. Without this line both rows below would be empty and the answer would be 0.
function rob(nums) { if (nums.length === 1) return nums[0]; const robRow = (row) => { let twoBack = 0; let oneBack = 0; for (const cash of row) { const best = Math.max(oneBack, twoBack + cash); twoBack = oneBack; oneBack = best; } return oneBack; }; const withoutFirst = robRow(nums.slice(1)); const withoutLast = robRow(nums.slice(0, -1)); return Math.max(withoutFirst, withoutLast);}The trap
Splitting the circle into two straight rows is the right move, and every circle of two or more houses comes out correct. But a circle of one house loses that house from both rows: nums.slice(1) and nums.slice(0, -1) are both empty, both rows give 0, and the answer is 0 instead of the house's cash. The single house needs its own check before the split.
function rob(nums) { const robRow = (row) => { let twoBack = 0; let oneBack = 0; for (const cash of row) { const best = Math.max(oneBack, twoBack + cash); twoBack = oneBack; oneBack = best; } return oneBack; }; // a single house is left out of both rows const withoutFirst = robRow(nums.slice(1)); const withoutLast = robRow(nums.slice(0, -1)); return Math.max(withoutFirst, withoutLast);}