House Robber II

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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));
}