House Robber II
MediumThe problem
nums[i] is the money in house i, and the houses are arranged in a circle, so the first and last houses are neighbours. You cannot rob two neighbouring houses. Return the most money you can rob.
- Example 1Input: nums = [2, 3, 2]Output: 3
Houses 0 and 2 are neighbours in the circle, so you can only rob house 1.
- Example 2Input: nums = [1, 2, 3, 1]Output: 4
Rob house 0 and house 2: 1 + 3.
- Example 3Input: nums = [1, 2, 3]Output: 3
Every pair of houses touches each other, so take the biggest one.
- 1 ≤ len(nums) ≤ 100
- 0 ≤ nums[i] ≤ 1,000
- With one house, the answer is nums[0]
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The street is a circle, so house 0 and house n−1 are neighbours. Break the circle.
The idea
Run House Robber twice — on houses [0..n−2] and [1..n−1] — and take the max (plus the n=1 special case).
Target: O(n) time, O(1) space
Go function shape
func rob(nums []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// RobCircle: houses form a circle, so the first and last cannot both be robbed.
// Solve the line twice (without the last house, then without the first) and take the better one.
func RobCircle(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
return max(Rob(nums[:len(nums)-1]), Rob(nums[1:]))
}