House Robber II

Same as House Robber, but the houses stand in a circle, so the first and last houses are neighbours.

A way to picture it

The same raccoon, but the bins now stand in a ring — so the first and last bins are neighbours too. Break the ring two ways: pretend the last bin doesn't exist, or pretend the first one doesn't. Solve each as a straight street and keep the better haul.

How to approach it

The first and last houses can't both be robbed. Answer = max(rob(houses 0…n−2), rob(houses 1…n−1)), with n = 1 handled separately.

Example

Input: {"nums":[2,3,2]}. Output: 3.

Complexity: O(n) time and O(1) space. Two linear passes.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.