💬 Discord
Sign In
NeetCode #661LC-213Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#661 · #213 · House Robber II(打家劫舍 II)

📌 Problem Statement & Constraints

The houses are now arranged in a circle, so the first and last houses are adjacent. Given nums, return the maximum amount you can rob without robbing two adjacent houses. Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 1000.

💡 Core Algorithmic Approaches

  1. In a circle the first and last houses cannot both be robbed, which splits the problem into two linear cases.
  2. Case A robs from houses 0..n - 2 (excluding the last); case B robs from 1..n - 1 (excluding the first).
  3. Run the linear House Robber recurrence on each range and return the larger result.
  4. The single-house input must be handled directly, since both ranges would otherwise be empty.

💻 Benchmark Python3 Implementation

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def linear(arr: List[int]) -> int:
            prev2, prev1 = 0, 0
            for x in arr:
                prev2, prev1 = prev1, max(prev1, prev2 + x)
            return prev1

        return max(linear(nums[:-1]), linear(nums[1:]))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two linear passes.
💾 Space Complexity
O(1) beyond the slices, which themselves cost O(n).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the single-house case: with n = 1 both nums[:-1] and nums[1:] are empty and the function would return 0 instead of nums[0].
  • Trying one circular DP: the first and last adjacency cannot be expressed in a single linear recurrence, hence the two-case split.
  • Excluding only the last house: the symmetric case of excluding the first can be strictly better, for example [1, 2, 3, 4, 5].
  • Believing the answer is always linear(nums[:-1]): neither case dominates in general, so both must be evaluated.