🧩 Problem Statement
You are a professional robber planning to rob houses along a street. Each house has some amount of money stashed. All houses are arranged in a circle, so the first and last house are adjacent.
You cannot rob two adjacent houses.
Return the maximum amount of money you can rob without alerting the police.
📘 Example
go
Input: nums = [2,3,2]
Output: 3
Explanation: Rob house 2 (money = 3) and not house 1 or 3.
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 and 3 (money = 1 + 3 = 4)
🧠 Approach
Since the houses are in a circle, we can't rob both the first and last house together.
So we run two separate linear House Robber I scenarios:
- Rob houses from index 0 to n-2
- Rob houses from index 1 to n-1
Then return the maximum of the two.
Use a helper function that solves the standard House Robber problem on a linear array.
✅ Go Implementation
go
package main
import "fmt"
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
return max(robLinear(nums[:n-1]), robLinear(nums[1:]))
}
func robLinear(nums []int) int {
prev1, prev2 := 0, 0
for _, num := range nums {
temp := max(prev1, prev2+num)
prev2 = prev1
prev1 = temp
}
return prev1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
📦 Example Usage
go
func main() {
fmt.Println(rob([]int{2, 3, 2})) // Output: 3
fmt.Println(rob([]int{1, 2, 3, 1})) // Output: 4
fmt.Println(rob([]int{0})) // Output: 0
}
⏱️ Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1) — optimized DP using two variables
🧠 Key Concepts
- Use dynamic programming to avoid overlapping subproblems.
- Special handling for circular structure via two linear passes.
- Rolling variables for optimal space usage.