House Robber II
You get a list nums where nums[i] is the amount of money in house i. The houses stand in a circle, so house 0 is next to the last house. You may rob any set of houses, but never two houses that are next to each other (including the first and the last).
Return the largest total you can rob.
Examples
Input nums = [2, 3, 2]
Output 3
Houses 0 and 2 are neighbors in the circle, so you cannot take both 2s.
Input nums = [1, 2, 3, 1]
Output 4
Rob houses 0 and 2.
Input nums = [7]
Output 7
Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1,000
Stuck? Take one hint at a time
Common mistakes
- Running the straight street solution once on the whole list, which allows robbing both the first and the last house.
- Forgetting the single house case, where both streets are empty and the answer would be 0.
- Leaving out the wrong house in the second street (using 0 to n - 2 twice).
- Reusing the same two variables between the two runs without resetting them.
Questions an interviewer may ask next
- Return which houses you rob, not only the total. (Remember the choices in the table and walk back.)
- The houses form a binary tree and a parent cannot be robbed together with a child. (House Robber III.)
- You may not rob three houses in a row, but two neighbors are fine. What is the new recurrence?
- At most k houses may be robbed. How does the table change? (Add a dimension for the count.)
nums
[2,3,2]
Expected output
3
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.