LeetCode 213: House Robber II Solution in Python Explained

Problem Statement

In LeetCode 213: House Robber II, you’re given:

• nums: An array of non-negative integers representing money in each house.
• The houses form a circle, so the first and last houses are adjacent.
• Your task is to return the maximum amount of money you can rob without robbing adjacent houses.

This extends LeetCode 198: House Robber by adding the circular constraint, differing from grid searches in LeetCode 212: Word Search II.

Constraints

• 1 ≤ nums.length ≤ 100.
• 0 ≤ nums[i] ≤ 1000.

Examples

Let’s see some cases:

Copy codeInput: nums = [2,3,2]
Output: 3
Explanation: Can’t rob 2 and 2 (adjacent via circle), so rob 3 (middle house).

Copy codeInput: nums = [1,2,3,1]
Output: 4
Explanation: Rob 1 (index 0) and 3 (index 2), total = 4.

Copy codeInput: nums = [1]
Output: 1
Explanation: Single house, rob 1.

These examples show the circular adjacency twist.

Understanding the Problem

How do we solve LeetCode 213: House Robber II in Python? For nums = [1,2,3,1], the circle means house 0 (1) and house 3 (1) are adjacent, so we can’t rob both. A naive recursive approach trying all combinations is exponential, but dynamic programming (DP) works since it’s a linear sequence with a circular constraint. We’ll split it into two cases: 1. Rob houses 0 to n-2 (exclude last). 2. Rob houses 1 to n-1 (exclude first). Take the maximum. We’ll use:

• DP with Two Cases: O(n) time, O(n) space—our best solution.
• DP with Space Optimization: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming with Two Cases Approach

Explanation

The DP with Two Cases approach splits the problem:

• Case 1: Exclude the last house (nums[0:n-1]), solve as a linear House Robber problem.
• Case 2: Exclude the first house (nums[1:n]), solve similarly.
• Use a helper DP function: dp[i] = max money up to house i, where dp[i] = max(dp[i-2] + nums[i], dp[i-1]).
• Return the maximum of the two cases.

This runs in O(n) time (two O(n) passes) and O(n) space (DP arrays), offering clarity and correctness—our best solution.

For [1,2,3,1], it computes [1,2,3] (max = 4) and [2,3,1] (max = 3), returning 4.

Step-by-Step Example

Example 1: nums = [1,2,3,1]

Goal: Return 4.

• Step 1: Define helper function.
• rob_linear(arr): Standard DP for linear array.
• Step 2: Case 1 (exclude last: [1,2,3]).
• dp[0] = 1 (rob 1).
• dp[1] = max(1, 2) = 2 (rob 2).
• dp[2] = max(dp[0] + 3, dp[1]) = max(4, 2) = 4 (rob 1, 3).
• Max = 4.
• Step 3: Case 2 (exclude first: [2,3,1]).
• dp[0] = 2.
• dp[1] = max(2, 3) = 3.
• dp[2] = max(dp[0] + 1, dp[1]) = max(3, 3) = 3.
• Max = 3.
• Step 4: Finish.
• max(4, 3) = 4.
• Output: 4.

Example 2: nums = [2,3,2]

Goal: Return 3.

• Step 1: Case 1 ([2,3]).
• dp[0] = 2.
• dp[1] = max(2, 3) = 3.
• Max = 3.
• Step 2: Case 2 ([3,2]).
• dp[0] = 3.
• dp[1] = max(3, 2) = 3.
• Max = 3.
• Step 3: max(3, 3) = 3.
• Output: 3.

How the Code Works (DP with Two Cases) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef rob(nums: list[int]) -> int:
    # Line 1: Handle edge cases
    if len(nums) == 1:
        # Single house (e.g., [1])
        return nums[0]
        # Return its value (e.g., 1)
    if len(nums) == 2:
        # Two houses, pick max (e.g., [2,3])
        return max(nums[0], nums[1])
        # Return max (e.g., 3)

    # Line 2: Helper function for linear case
    def rob_linear(arr):
        # Solve standard House Robber
        if not arr:
            return 0
        dp = [0] * len(arr)
        # DP array (e.g., [0,0,0])
        dp[0] = arr[0]
        # First house (e.g., 1)
        dp[1] = max(arr[0], arr[1])
        # Max of first two (e.g., 2)

        for i in range(2, len(arr)):
            # Iterate remaining houses (e.g., i=2)
            dp[i] = max(dp[i-2] + arr[i], dp[i-1])
            # Choose max of including i or not (e.g., max(1+3, 2)=4)

        return dp[-1]
        # Return max loot (e.g., 4)

    # Line 3: Split into two cases
    case1 = rob_linear(nums[:-1])
    # Exclude last house (e.g., [1,2,3])
    case2 = rob_linear(nums[1:])
    # Exclude first house (e.g., [2,3,1])

    # Line 4: Return maximum
    return max(case1, case2)
    # Max of two cases (e.g., max(4, 3)=4)

This solution is clear and leverages DP effectively.

Alternative: DP with Space Optimization Approach

Explanation

The DP with Space Optimization approach avoids arrays:

• Use two variables (prev2, prev1) to track max loot from two and one house back.
• Run two passes (exclude first, exclude last) with this space-efficient DP.
• Return the maximum.

It’s O(n) time and O(1) space, trading clarity for memory savings.

Step-by-Step Example

For [1,2,3,1]:

• Case 1: [1,2,3]:
• prev2 = 0, prev1 = 1.
• i=1: curr = max(0+2, 1)=2, prev2=1, prev1=2.
• i=2: curr = max(1+3, 2)=4, prev2=2, prev1=4.
• Max = 4.
• Case 2: [2,3,1]:
• prev2 = 0, prev1 = 2.
• i=1: curr = max(0+3, 2)=3.
• i=2: curr = max(2+1, 3)=3.
• Max = 3.
• Output: max(4, 3)=4.

How the Code Works (Space Optimized)

Copy codedef robSpaceOptimized(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        return max(nums[0], nums[1])

    def rob_linear(arr):
        prev2, prev1 = 0, arr[0]
        for i in range(1, len(arr)):
            curr = max(prev2 + arr[i], prev1)
            prev2, prev1 = prev1, curr
        return prev1

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

Complexity

• DP with Two Cases:
• Time: O(n) – two linear passes.
• Space: O(n) – DP arrays.
• DP with Space Optimization:
• Time: O(n) – two linear passes.
• Space: O(1) – two variables.

Efficiency Notes

DP with Two Cases is our best solution for its readability and straightforward logic. Space Optimization saves memory but is less intuitive.

Key Insights

• Circular: Split into linear cases.
• DP: Optimal substructure.
• Adjacency: Core constraint.

Additional Example

For [2,7,9,3,1]:

• Case 1: [2,7,9,3], max = 11 (2+9).
• Case 2: [7,9,3,1], max = 10 (7+3).
• Output: 11.

Edge Cases

• Single house: [1], 1.
• Two houses: [1,2], 2.
• All zeros: [0,0], 0.

Both handle these well.

Final Thoughts

LeetCode 213: House Robber II in Python is a clever DP twist. DP with Two Cases shines with clarity, while Space Optimization offers efficiency. Want more? Try LeetCode 198: House Robber or LeetCode 337: House Robber III. Test your skills—Solve LeetCode 213 on LeetCode with [1,2,3,1] (expecting 4)—plan that heist today!