House Robber II

• Difficulty: Medium
• Topics: Array, Dynamic Programming
• Link: https://leetcode.com/problems/house-robber-ii/

Problem Description

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. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Solution

1. Problem Deconstruction

Technical Description
Given a circular array nums where each element represents money in a house, find the maximum sum obtainable by selecting non-adjacent elements. Adjacency includes the first and last elements (circular constraint).

Beginner Description
You’re a thief robbing houses arranged in a circle. You can’t rob two houses next to each other (including the first and last). Maximize your loot.

Mathematical Formulation
Let nums[0...n-1] be the input array. Maximize S = Σ nums[i] such that:

• No two indices in S are consecutive modulo n (i.e., i and i+1 or 0 and n-1).

Constraint Analysis

1. 1 <= nums.length <= 100:
   • Limits solution to polynomial time (e.g., DP with O(n) is feasible).
   • Edge Case: Single house → return nums[0].
2. 0 <= nums[i] <= 1000:
   • No negative values → greedy selection of non-adjacent houses is valid.
   • Edge Case: All zeros → result is 0.

---

2. Intuition Scaffolding

Analogies

1. Real-World: Circular art gallery with motion sensors between adjacent rooms. Steal art without triggering alarms.
2. Gaming: Collecting coins in a circular maze where stepping on adjacent tiles alerts guards.
3. Math: Maximum independent set on a circular graph with nodes as houses.

Common Pitfalls

1. Circular Blindness: Ignoring the first-last adjacency (e.g., treating it as linear).
2. Double-Counting: Including both first and last in separate scenarios.
3. Over-Reduction: Assuming the optimal is max(nums[0], nums[-1]) for small n.
4. Edge Neglect: Failing to handle n=1 or n=2 explicitly.
5. Greedy Fallacy: Picking odd/even indices without considering circularity.

---

3. Approach Encyclopedia

Optimal Approach: Split DP

• Strategy: Break the circle into two linear problems:
  1. Rob houses 0 to n-2 (exclude last).
  2. Rob houses 1 to n-1 (exclude first).
• Use the original House Robber DP for each subproblem.

Pseudocode

def rob(nums):  
    if len(nums) == 1:  
        return nums[0]  
    return max(helper(nums, 0, len(nums)-2),  
               helper(nums, 1, len(nums)-1))  

def helper(nums, start, end):  
    prev, curr = 0, 0  
    for i in range(start, end + 1):  
        new_curr = max(curr, prev + nums[i])  
        prev, curr = curr, new_curr  
    return curr  

Complexity Proof

• Time: Two passes over n-1 elements → $O(n) + O(n) = O(n)$.
• Space: Constant variables prev and curr → $O(1)$.

Visualization
For nums = [1,2,3,1]:

• Scenario 1 (0-2):

  Houses: [1, 2, 3] → DP steps: [0,1] → [1,2] → [2,4] → Result: 4  
  

• Scenario 2 (1-3):

  Houses: [2, 3, 1] → DP steps: [0,2] → [2,3] → [3,3] → Result: 3  
  

---

4. Code Deep Dive

Line-by-Line Breakdown

def rob(nums):  
    # Edge case: single house  
    if len(nums) == 1:  # O(1) check  
        return nums[0]  
    # Split into two linear subproblems  
    return max(  
        helper(nums, 0, len(nums)-2),  # Exclude last house  
        helper(nums, 1, len(nums)-1)   # Exclude first house  
    )  

def helper(nums, start, end):  
    prev, curr = 0, 0  # Track DP states  
    for i in range(start, end + 1):  
        # Compute new_curr as max(skip current vs rob current)  
        new_curr = max(curr, prev + nums[i])  
        prev, curr = curr, new_curr  # Update states  
    return curr  # Final result for subarray  

Edge Case Handling

• Example 1 (nums = [2,3,2]):
  helper(0,1) → max(2,3) = 3; helper(1,2) → max(3,2) = 3. Result: 3.
• Example 3 (nums = [1,2,3]):
  helper(0,1) → 2; helper(1,2) → 3. Result: 3.

---

5. Complexity War Room

Hardware Considerations

• For n=100, two passes → ~200 operations. Fits in CPU cache (negligible memory footprint).

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(2ⁿ)	O(1)	Low	❌ (Fails n > 20)
Split DP	O(n)	O(1)	High	✅ (Optimal)

---

6. Pro Mode Extras

Variants

• House Robber III (Tree): DFS with memoization (LC 337).
• k Transactions: Extend DP to track states for multiple buys/sells (LC 188).

Interview Cheat Sheet

• Key Insight: Split circular problem into two linear subproblems.
• Mention: Time/space complexity first, then edge cases.
• Test Cases: Always test n=1, n=2, and circular adjacency cases.