House Robber II
Medium · 1-D Dynamic Programming
Houses are arranged in a circle, and an array of integers gives the amount of cash stored in each house in order around the circle. You may rob any subset of houses, but you can never rob two houses that are adjacent, and because the arrangement is circular the first and last houses count as adjacent too. Return the maximum total amount of cash you can collect without robbing two neighboring houses.
Examples
Input: nums = [2,3,2]
Output: 3
Why: Robbing house 0 and house 2 is not allowed since they are adjacent in the circle, so the best choice is just house 1 with value 3.Input: nums = [1,2,3,1]
Output: 4
Why: Robbing house 0 (value 1) and house 2 (value 3) gives 4, which beats any other non-adjacent combination in this circle.Input: nums = [1,2,3]
Output: 3
Why: All three houses are mutually adjacent in a circle of size 3, so only one house can be robbed, and the best value is 3.Constraints
1 <= nums.length <= 10^4, 0 <= nums[i] <= 1000
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of House Robber II. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.