🟨 House Robber II (#213)
🔗 Problem Link
📋 Problem Statement
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Adjacent houses have security systems connected.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
💡 Examples
Example 1
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 and house 3 since they are adjacent.
Example 2
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 1 + 3 = 4.
🔑 Key Insights & Approach
Core Observation: First and last houses are connected. Solve House Robber I twice: once excluding first, once excluding last.
Why Two Passes?
- Can't rob both first and last
- Run House Robber I on [0...n-2] and [1...n-1]
- Return max of both
- O(n) time, O(1) space
Pattern: "Circular Array DP" - break circle into linear cases.
🐍 Solution: Python
Approach: Two Pass House Robber I
Time Complexity: O(n) | Space Complexity: O(1)
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
def rob_linear(houses):
prev2, prev1 = 0, 0
for num in houses:
current = max(prev1, prev2 + num)
prev2 = prev1
prev1 = current
return prev1
# Rob houses [0...n-2] or [1...n-1]
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
🔵 Solution: Golang
Approach: Two Pass
Time Complexity: O(n) | Space Complexity: O(1)
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
if n == 2 {
return max(nums[0], nums[1])
}
robLinear := func(houses []int) int {
prev2, prev1 := 0, 0
for _, num := range houses {
current := max(prev1, prev2+num)
prev2 = prev1
prev1 = current
}
return prev1
}
return max(robLinear(nums[:n-1]), robLinear(nums[1:]))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}