Dynamic Programming · 119Medium
House Robber II
The houses are arranged in a CIRCLE, so the first and last are adjacent. You cannot rob two adjacent houses. Return the maximum you can rob.
Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
Examples
rob([2, 3, 2]) -> 3 // cannot take both 2s, they are adjacent rob([1, 2, 3, 1]) -> 4 rob([1, 2, 3]) -> 3 rob([5]) -> 5 // a single house rob([2, 7]) -> 7 // two houses — take the larger rob([1, 3, 1, 3, 100]) -> 103 // houses 1 and 4 are not adjacent
Edge cases
- A single house — the circle rule cannot apply.
- Two houses — take the larger.
- The first and last houses can never BOTH be robbed.
Show the target complexity (spoiler)
- Naive
- O(2^n) time — enumerate every subset and reject adjacent picks, now including the
- Target
- O(n) time, O(1) space — run the linear House Robber twice, once excluding the last house and once excluding the first, and take the better.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/119-house-robber-ii.js ./practice c 119