House Robber | Leetcode 198
Welcome to our definitive, multi-stage breakdown of the House Robber problem (Leetcode 198). This is one of the most quintessential Dynamic Programming (DP) questions you will ever encounter in technical interviews. It perfectly demonstrates the evolution of an algorithm from a slow, naive recursive solution all the way to a highly optimized, constant-space DP approach.
Problem Statement
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, but the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected. 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 at each house, return the maximum amount of money you can rob tonight without alerting the police.
Example:
nums = [2, 7, 9, 3, 1] => Output: 12
(Rob house 1 (money=2), rob house 3 (money=9), rob house 5 (money=1) for a total of 12).
Approach 1: Recursive Brute Force (Top-Down)
Let's break down the logic recursively. If we are standing at the last house (index i), we have exactly two choices:
- Rob this house: If we rob house
i, we getnums[i], but we are forbidden from robbing housei-1. The next house we can safely rob isi-2. - Skip this house: If we skip house
i, we get0from it, and we move on to try and rob housei-1.
This gives us our recursive recurrence relation:
rob(i) = max(rob(i - 2) + nums[i], rob(i - 1))
class Solution:
def rob(self, nums: List[int]) -> int:
def helper(i):
if i < 0:
return 0
return max(helper(i - 2) + nums[i], helper(i - 1))
return helper(len(nums) - 1)
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | O(2^N) | At every step we branch out into two recursive calls, creating a massive, overlapping recursion tree. This will Result in a Time Limit Exceeded (TLE) on LeetCode. |
| Space | O(N) | Memory consumed by the recursion call stack proportional to the maximum depth of the DP tree. |
Approach 2: Top-Down Memoization
The fundamental flaw of the Brute Force approach is that it recalculates the exact same subproblems repeatedly. If we decide to skip house 4, we calculate the max profit for houses 0-3. But if we rob house 5, we also calculate the max profit for houses 0-3.
We can optimize this significantly by "caching" (memoizing) the result of a subproblem the first time we calculate it.
class Solution:
def rob(self, nums: List[int]) -> int:
memo = {}
def helper(i):
if i < 0:
return 0
if i in memo:
return memo[i]
memo[i] = max(helper(i - 2) + nums[i], helper(i - 1))
return memo[i]
return helper(len(nums) - 1)
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | O(N) | We only ever calculate the max() for a specific index one time. Subsequent calls retrieve the O(1) cached result. |
| Space | O(N) | We allocate an explicit memo Dictionary/Array of size N on top of the O(N) internal recursion stack. |
Approach 3: Bottom-Up Dynamic Programming (1D Array)
Recursion is heavily reliant on the system call stack, which can lead to Stack Overflow errors on massive inputs. We can invert our thinking and build the solution iteratively from the "bottom up" using an array dp.
dp[i] represents the maximum money we can rob up to index i.
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
graph LR
subgraph Iteration
A["nums = [2]"] --> B("dp[0] = 2")
C["nums = [2, 7]"] --> D("dp[1] = max(2, 7) = 7")
E["nums = [2, 7, 9]"] --> F("dp[2] = max(7, 2 + 9) = 11")
G["nums = [2, 7, 9, 3]"] --> H("dp[3] = max(11, 7 + 3) = 11")
I["nums = [2, 7, 9, 3, 1]"] --> J("dp[4] = max(11, 11 + 1) = 12")
end
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | O(N) | We iterate exactly once through the sequence. |
| Space | O(N) | We construct a 1-Dimensional dp array tracking max profit exactly mirroring the size of the input. |
Approach 4: Optimal Bottom-Up DP (O(1) Space)
Finally, we arrive at the optimal solution. Take a close look at our dp array loop:
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
Notice that to calculate the current house dp[i], we only ever need the values of the previous two houses (dp[i-1] and dp[i-2]). The entire rest of the O(N) array is completely ignored!
We can discard the array and simply cycle through two variables, rob1 and rob2.
class Solution:
def rob(self, nums: List[int]) -> int:
rob1, rob2 = 0, 0
# [rob1, rob2, n, n+1, ...]
for n in nums:
temp = max(n + rob1, rob2)
rob1 = rob2
rob2 = temp
return rob2
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | O(N) | Single iterating pass over the elements making immediate max() calculations. |
| Space | O(1) | Constant space constraints achieved by discarding the DP array and pointer-swapping with just rob1 and rob2! (Optimal). |
Next Steps
Once you master this logic, you are ready to tackle its direct sequel: House Robber II, where the houses are arranged in a massive circle! Watch the embedded video above for a visual whiteboard walkthrough.