House Robber | Leetcode 198 | Brute Force and Optimal Solutions

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Here’s the [Problem Link] to begin with.

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 = [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 2:

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

Constraints:

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

Solution 1: Brute Force Approach (Pure Recursion)

Intuition

Imagine standing at the last house: you have a choice—rob it (and skip the previous one) or skip it (and take the max from the previous). This decision repeats for every house backward. Recursively, for each index, compute the max by either “picking” (rob current + max from index-2) or “not picking” (max from index-1), and choose the better one. It’s like exploring a decision tree where each node is a house, and branches are rob or skip.

Detailed Approach

• Base Cases: If index == 0, rob nums. If index == -1, return 0 (no houses).
• Recursive Case: For index >= 1, max(pick = nums[index] + solve(index-2), notpick = solve(index-1)).
• No Optimization: Recalculate subproblems repeatedly, leading to exponential time.
• Tree Structure: Binary tree of decisions with overlaps (e.g., solve(2) called multiple times).

Code

class Solution:
    def solve(self, index, nums):
        if index == 0:
            return nums[index]
        if index == -1:
            return 0
        pick = nums[index] + self.solve(index - 2, nums)
        notpick = 0 + self.solve(index - 1, nums)
        return max(pick, notpick)

    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        return self.solve(n - 1, nums)

Code Explanation

The solve function recursively computes the max robbery amount up to the given index. It handles base cases for index 0 (return nums) and -1 (return 0). For other indices, it calculates ‘pick’ by adding the current house’s value to the result from two houses back, and ‘notpick’ from the immediate previous house, then returns the maximum. The rob function starts the recursion from the last index. This models the rob/skip choices but with redundant computations.

Time and Space Complexity

Time Complexity: O(2^n) – Each call branches into 2, exponential growth.

Space Complexity: O(n) – Recursion stack depth up to n.

Simplifying It

This is like trying every possible robbery path by revisiting the same streets multiple times, intuitive but wasteful, as you forget what you’ve already calculated for earlier houses!

Solution 2: Memoization Approach (Top-Down Dynamic Programming)

Intuition

The brute force recomputes subproblems (e.g., max for house 3 calculated repeatedly). Add a “memory” (DP array) to store results: check if already computed for an index, return it; else compute, store, and return. This caches decisions, turning the tree into a DAG (directed acyclic graph) with no repeats.

Detailed Approach

• Memoization Array: dp of size n, initialized to -1.
• Check Cache: In solve, if dp[index] != -1, return it.
• Compute and Store: Else, calculate pick/notpick, store max in dp[index].
• Same Structure: Retains recursive choices but with caching.
• One-Time: Each index computed once.

Code

class Solution:
    def solve(self, index, nums, dp):
        if index == 0:
            return nums[index]
        if index == -1:
            return 0
        if dp[index] != -1:
            return dp[index]
        pick = nums[index] + self.solve(index - 2, nums, dp)
        notpick = 0 + self.solve(index - 1, nums, dp)
        dp[index] = max(pick, notpick)
        return dp[index]

    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1] * n
        return self.solve(n - 1, nums, dp)

Code Explanation

Extends recursion with dp array. Before computing, check if dp[index] is set; if yes, return it. Otherwise, compute pick (rob current + recurse index-2) and notpick (recurse index-1), store the max in dp, and return. This ensures each subproblem is solved once, reusing stored values for efficiency.

Time and Space Complexity

Time Complexity: O(n) – Each index computed once.

Space Complexity: O(n) – dp array + O(n) stack.

Simplifying It

Like the brute force, but with a notebook: jot down the max loot from each house onward, and check your notes before recalculating, saves tons of time!

Solution 3: Tabulation Approach (Bottom-Up Dynamic Programming)

Intuition

Flip the recursion: start from house 0 and build up. Use a DP array where dp[i] = max loot up to house i. For each i, dp[i] = max(nums[i] + dp[i-2], dp[i-1]) (if i>1). This iteratively fills from base cases, avoiding recursion.

Detailed Approach

• Initialize DP: dp = nums.
• Bottom-Up: For i=1 to n-1, pick = nums[i] + (dp[i-2] if i>1 else 0), notpick = dp[i-1], dp[i]=max.
• Sequential: Dependencies resolved in order.
• No Recursion: Loop-based, no stack.

Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1] * n
        dp[0] = nums[0]
        for index in range(1, n):
            if index > 1:
                pick = nums[index] + dp[index - 2]
            else:
                pick = nums[index]
            notpick = 0 + dp[index - 1]
            dp[index] = max(pick, notpick)
        return dp[n - 1]

Code Explanation

Initialize dp to nums. Loop from 1 to n-1: compute pick (rob current + dp[index-2] if possible, else just nums[index]), notpick (dp[index-1]), store max in dp[index]. Returns dp[n-1]. Builds max loot progressively using prior values.

Time and Space Complexity

Time Complexity: O(n) – Loop with O(1) per iteration.

Space Complexity: O(n) – dp array.

Simplifying It

Like mapping out the street from the start, noting max loot at each house based on the previous ones—organized and no backtracking!

Solution 4: Space-Optimized Tabulation (Optimal Approach)

Intuition

We only need the last two dp values. Use variables prev (dp[i-1]) and prev2 (dp[i-2]), update as we go: curr = max(nums[i] + prev2, prev), then shift.

Detailed Approach

• Initialize: prev = nums, prev2 = 0.
• Sliding Window: For i=1 to n-1, pick = nums[i] + prev2 (if i>1 else nums[i]), notpick=prev, curr=max, update prev2=prev, prev=curr.
• Constant Space: Just variables.

Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        prev = nums[0]
        prev2 = 0
        for index in range(1, n):
            if index > 1:
                pick = nums[index] + prev2
            else:
                pick = nums[index]
            notpick = 0 + prev
            curr = max(pick, notpick)
            prev2 = prev
            prev = curr
        return prev

Code Explanation

Start with prev=nums, prev2=0. For each index, compute pick/notpick using prev/prev2, set curr to max, update prev2 to prev and prev to curr. Prev holds the final max. Simulates DP with minimal space.

Time and Space Complexity

Time Complexity: O(n) – Loop.

Space Complexity: O(1) – Few variables.

Simplifying It

Like scouting the street while only remembering the max from the last two houses—efficient and forgetful of unnecessary details!

Summary

The space-optimized version is ideal for interviews,shows full optimization! This problem relates to Fibonacci-like sequences.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.