House Robber II
Problem
Houses stand in a circle, so the first and last are neighbours. You cannot rob two adjacent houses. Return the maximum amount you can rob.
Example 1
Input: [2, 3, 2] Output: 3
Houses 0 and 2 are adjacent in the circle.
Example 2
Input: [1, 2, 3, 1] Output: 4
Test cases
Case 1
Input: [2,3,2] Expected: 3
Case 2
Input: [1,2,3,1] Expected: 4
Case 3
Input: [1,2,3] Expected: 3
Case 4
Input: [5] Expected: 5
View solutionHide solution1 approach
1. Two linear runs
Time O(n)Space O(1)
Houses form a circle, so the first and last cannot both be robbed. Answer = max(rob 0..n−2, rob 1..n−1) using the linear House Robber.
function rob(nums) { if (nums.length === 1) return nums[0]; const line = (lo, hi) => { let prev = 0, cur = 0; for (let i = lo; i <= hi; i++) [prev, cur] = [cur, Math.max(cur, prev + nums[i])]; return cur; }; return Math.max(line(0, nums.length - 2), line(1, nums.length - 1));}