Problem
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.
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.
Examples
Example 1:
|
|
Example 2:
|
|
Similar Problems
House Robber 2 - Houses in circle House Robber 3 - Houses in Binary Tree House Robber 4
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Naive
The naive approach computes the largest possible amount of money we can rob by explicitly examining all potential combinations of houses.
The idea is simple:
- At every house, we have two choices:
- Either, Rob the house (add the house’s money to the total and skip the adjacent house).
- or Skip it ( and move to the next house).
- Take the maximum amount of money between these two choices.
rob(i) = max(rob(i+1), nums[i] + rob(i+2))
- Continue evaluating recursively for the rest of the houses.
This is how the recursion tree looks for example 2 [2, 7, 9, 3, 1]
:
graph TD rob0["rob(0) (choose 2)"] rob0 --> rob0case["2 + rob(2)"] rob0 --> skip0["rob(1) (skip 2)"] rob0case --> rob2case["9 + rob(4)"] rob0case --> skip2["rob(3) (skip 9)"] skip0 --> rob1case["7 + rob(3)"] skip0 --> skip1["rob(2) (skip 7)"] rob2case --> rob4case["1 + rob(5)"] rob2case --> skip5["rob(5) (skip 1)"] skip2 --> rob3case["3 + rob(5)"] skip2 --> skip4["rob(4) (skip 3)"] rob1case --> rob3subcase["3 + rob(5)"] rob1case --> skip3["rob(4) (skip 3)"] skip1 --> rob2alt["9 + rob(4)"] skip1 --> skip3alt["rob(3) (skip 9)"] rob3case --> base1["Base Case: 0"] skip4 --> base2["Base Case: 1"] rob4case --> base3["Base Case: 0"] skip5 --> base4["Base Case: 0"] rob2alt --> base5["Base Case: 1"] skip3 --> base6["Base Case: 1"] rob3subcase --> base7["Base Case: 0"] skip3alt --> base8["Base Case: 1"]
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(2^n)
. Each house creates two recursive calls (rob(i+1)
androb(i+2)
), leading to exponential growth in the recursion tree. - 🧺 Space complexity:
O(n)
. The recursion depth in the call stack can reach up ton
(the number of houses).
Method 2 - Top-down DP with Memoization
In the naive approach, we have a lot of repeating subproblems, which we can cache the first time we compute them and reuse them later.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
. Each house index is computed only once and stored in the cache. - 🧺 Space complexity:
O(n)
. The recursion stack can go as deep asn
, and the cache stores up ton
results.
Method 3 - Bottom-up Dynamic Programming
Here are the steps:
- Initialise a DP Array: Create an array
dp
of sizen
(number of houses). - Set the Base Cases:
dp[0] = nums[0]
- If there are at least two houses,
dp[1] = max(nums[0], nums[1])
.
- Iteratively Fill the DP Array:
- Start from the third house (
i = 2
) and calculate:dp[i] = max(nums[i] + dp[i-2], dp[i-1])
- Move from the beginning to the end of the array, updating the array step by step.
- Start from the third house (
- Result:
- The value in
dp[n-1]
(the last cell of the DP array) will be the maximum amount of money that can be robbed.
- The value in
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
. Filling thedp
array requires iterating through alln
houses. - 🧺 Space complexity:
O(n)
. Thedp
array uses O(n) space to store intermediate results.
Method 4 - Space-optimized bottom up DP
When we look closely at the recurrence relation:
|
|
Each result `dp[i]` depends only on the previous two values (`dp[i-1]` and `dp[i-2]`) and **not the entire DP array**.
- So, instead of maintaining a full
dp
array, we can optimise space by using two variables:prev1
: Representsdp[i-1]
(the maximum loot up to the previous house).prev2
: Representsdp[i-2]
(the maximum loot up to two houses behind).- This approach is similar to other problems, like generating the nth Fibonacci number.
- As we iterate through the houses, these two variables are dynamically updated to compute the result.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
, as we iterate through alln
houses once. - 🧺 Space complexity:
O(1)
, as we only use two variables (prev1
andprev2
) for intermediate computations.
Method 5 - Bottom-up Dynamic Programming but starting from behind
We can also use bottom up dp approach, by starting from the end of the array. The dp recurrence relation is then similar to recursive top down approach. Here are the steps:
- Instead of starting from the first house (as in recursion), we solve the problem backwards (from the last house to the first house).
- We’ll use a DP array (
dp
) where eachdp[i]
represents the maximum amount of money that can be robbed starting from housei
. - Base Cases:
- If there’s no house (
i >= n
),dp[i] = 0
. - If there’s one house at the end (
dp[n-1]
),dp[n-1] = nums[n-1]
.
- If there’s no house (
- The relationship remains the same as in the recursive approach:
dp[i] = max(nums[i] + dp[i+2], dp[i+1])
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
. Filling thedp
array takesO(n)
time, as we iterate through all houses once. - 🧺 Space complexity:
O(n)
. Thedp
array requiresO(n + 1)
space, which is proportional to the number of houses.