LeetCode 198: House Robber Solution in Python Explained

Problem Statement

In LeetCode 198, you’re given an integer array nums where nums[i] is the amount of money in house i. Your task is to return the maximum amount you can rob, subject to:

• You cannot rob adjacent houses (e.g., if you rob house i, you skip i+1).
• Return the maximum possible integer profit.

This differs from SQL queries like LeetCode 197: Rising Temperature, focusing on dynamic programming rather than temporal data analysis.

Constraints

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

Example

Let’s see some cases:

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

Copy codeInput: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 0 (2), house 2 (9), and house 4 (1), total = 12 (2+9+1).

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

These examples show we’re maximizing non-adjacent sums.

Understanding the Problem

How do you solve LeetCode 198: House Robber in Python? Take nums = [2,7,9,3,1]. We need the max profit without robbing adjacent houses. Possible combinations:

• House 0 (2), 2 (9), 4 (1) → 12.
• House 1 (7), 3 (3) → 10.
• House 0 (2), 2 (9) → 11.

Brute-forcing all combinations is exponential (O(2^n)), so we need dynamic programming (DP) to optimize by building the solution incrementally. This isn’t a bit-counting task like LeetCode 191: Number of 1 Bits; it’s about optimizing a sequence. We’ll use: 1. Dynamic Programming with Two Variables: O(n) time, O(1) space—our best solution. 2. Recursive with Memoization: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming with Two Variables Approach

Explanation

Dynamic Programming with Two Variables maximizes profit by:

• Using two variables: prev (max profit excluding current house) and curr (max profit including current house).
• For each house i:
• New prev = old curr (exclude current).
• New curr = max(old curr, old prev + nums[i]) (include current or not).
• Iterate through nums, updating variables.

This achieves O(n) time (single pass), O(1) space (two variables), and efficiency by avoiding array storage, making it optimal.

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

• Start: prev=0, curr=2.
• i=1: curr=7 (max(2, 0+7)), prev=2.
• i=2: curr=11 (max(7, 2+9)), prev=7.
• i=3: curr=11 (max(11, 7+3)), prev=11.
• i=4: curr=12 (max(11, 11+1)), prev=11.
• Result: 12.

Step-by-Step Example

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

Goal: Return 12.

• Step 1: Initialize.
• prev = 0 (no houses robbed), curr = 0.
• Step 2: Iterate through nums.
• i=0 (2):
• temp = curr → 0.
• curr = max(curr, prev + nums[0]) → max(0, 0+2) = 2.
• prev = temp → 0.
• State: prev=0, curr=2.
• i=1 (7):
• temp = 2.
• curr = max(2, 0+7) = 7.
• prev = 2.
• State: prev=2, curr=7.
• i=2 (9):
• temp = 7.
• curr = max(7, 2+9) = 11.
• prev = 7.
• State: prev=7, curr=11.
• i=3 (3):
• temp = 11.
• curr = max(11, 7+3) = 11.
• prev = 11.
• State: prev=11, curr=11.
• i=4 (1):
• temp = 11.
• curr = max(11, 11+1) = 12.
• prev = 11.
• State: prev=11, curr=12.
• Step 3: Return curr.
• 12.
• Finish: Return 12.

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

Goal: Return 4.

• Step 1: prev=0, curr=0.
• Step 2: Iterate:
• i=0 (1): curr=1, prev=0.
• i=1 (2): curr=2, prev=1.
• i=2 (3): curr=4, prev=2.
• i=3 (1): curr=4, prev=4.
• Finish: Return 4.

How the Code Works (Dynamic Programming with Two Variables) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef rob(nums: list[int]) -> int:
    # Line 1: Handle edge cases
    if not nums:
        # Empty array (e.g., [])
        return 0
    if len(nums) == 1:
        # Single house (e.g., [1])
        return nums[0]

    # Line 2: Initialize variables
    prev = 0
    # Max profit excluding current (e.g., 0 initially)
    curr = 0
    # Max profit including current (e.g., 0 initially)

    # Line 3: Iterate through houses
    for num in nums:
        # Each house value (e.g., 2, 7, 9, 3, 1)

        # Line 4: Store current max
        temp = curr
        # Temp holds old curr (e.g., 0, then 2)

        # Line 5: Update curr with max profit
        curr = max(curr, prev + num)
        # Include current or not (e.g., max(0, 0+2)=2)

        # Line 6: Update prev
        prev = temp
        # Previous max (e.g., 0, then 2)

    # Line 7: Return maximum profit
    return curr
    # e.g., 12

This detailed breakdown clarifies how DP with two variables efficiently maximizes profit.

Alternative: Recursive with Memoization Approach

Explanation

Recursive with Memoization maximizes profit by:

• Defining dp(i): Max profit from house i onward.
• Base case: i ≥ n → 0.
• Recurse: Max of rob i (skip i+1) or skip i.
• Memoize to avoid recomputation.

It’s a practical alternative, O(n) time (memoized calls), O(n) space (memo table), but uses more memory and recursion overhead.

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

• dp(0): Max(2+dp(2), dp(1)) → 12.
• Computes top-down, memoizes results.

Step-by-Step Example (Alternative)

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

• dp(0): Max(2+dp(2), dp(1)).
• dp(2): Max(9+dp(4), dp(3)) = 10.
• dp(1): Max(7+dp(3), dp(2)) = 10.
• Max(2+10, 10) = 12.
• Finish: Return 12.

How the Code Works (Recursive)

Copy codedef robRecursive(nums: list[int]) -> int:
    memo = { {
    def dp(i: int) -> int:
        if i >= len(nums):
            return 0
        if i in memo:
            return memo[i]
        memo[i] = max(dp(i+1), nums[i] + dp(i+2))
        return memo[i]
    return dp(0)

Complexity

• Dynamic Programming with Two Variables:
• Time: O(n) – single pass.
• Space: O(1) – two variables.
• Recursive with Memoization:
• Time: O(n) – memoized calls.
• Space: O(n) – memo table.

Efficiency Notes

Dynamic Programming with Two Variables is the best solution with O(n) time and O(1) space, offering simplicity and minimal memory—Recursive with Memoization matches time complexity but uses O(n) space and recursion, making it less efficient but still effective.

Key Insights

• Two Vars: Space-efficient DP.
• Memo: Top-down caching.
• Non-Adjacent: Core constraint.

Additional Example

For nums = [1,3,1]:

• Goal: 3.
• DP: prev=0, curr=1, curr=3, curr=3.

Edge Cases

• Empty: 0.
• Single: Value of house.
• Two Houses: Max of two.

Both solutions handle these well.

Final Thoughts

LeetCode 198: House Robber in Python is a classic DP challenge. The Dynamic Programming with Two Variables solution excels with its efficiency and elegance, while Recursive with Memoization offers a recursive approach. Want more? Try LeetCode 213: House Robber II for a circular twist or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 198 on LeetCode with [2,7,9,3,1], aiming for 12—test your skills now!