House Robber II

The key idea

The houses form a circle, so the first and last are adjacent — you can never rob both. That single coupling is the whole twist. Break the circle by running the plain linear House Robber twice: once on houses [0 .. n-2] (drop the last) and once on [1 .. n-1] (drop the first). Each pass is a clean line with no wrap-around, and the answer is the larger of the two.

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Examples

Input: nums = [2,3,2] Output: 3

Input: nums = [1,2,3,1] Output: 4

Input: nums = [1,2,3] Output: 3

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →