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.
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 <= 1000 <= nums[i] <= 400Problem Overview: You are given an array where each element represents money stored in a house along a street. Adjacent houses cannot be robbed on the same night because they trigger an alarm. The goal is to compute the maximum amount of money you can steal without robbing two neighboring houses.
Approach 1: Dynamic Programming - Iterative DP Array (O(n) time, O(n) space)
This problem fits the classic dynamic programming pattern where each decision depends on previous optimal results. Define dp[i] as the maximum money you can rob from the first i houses. For each house, you either rob it or skip it. If you rob house i, you add its value to dp[i-2]. If you skip it, you keep dp[i-1]. The recurrence becomes dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Iterate through the array, computing the best outcome at each step.
This approach explicitly stores results for every house, making the logic easy to visualize and debug. It clearly shows how the problem reduces to choosing between two previous states. The tradeoff is extra memory proportional to the number of houses.
Approach 2: Dynamic Programming - Optimized Space (O(n) time, O(1) space)
The DP recurrence only depends on the previous two states: dp[i-1] and dp[i-2]. Instead of maintaining a full array, keep two variables representing these values. As you iterate through the houses, compute the current best value and shift the variables forward.
At each step, calculate current = max(prev1, prev2 + num), where prev1 stores the best result up to the previous house and prev2 stores the best result two houses back. Update the variables as you move forward. This keeps the same decision logic while eliminating the DP array.
This version is the standard optimal solution discussed in interviews. It still performs a single pass through the array and maintains constant memory usage. The algorithm behaves like a rolling dynamic programming window that tracks only the necessary states.
Recommended for interviews: Start by explaining the DP recurrence using the array-based solution since it clearly demonstrates the decision process between robbing and skipping a house. Then optimize it to the constant-space version. Interviewers usually expect the O(n) time, O(1) space solution because it shows strong understanding of dynamic programming state transitions and space optimization.
This approach uses a dynamic programming table, where we maintain an array 'dp' such that dp[i] represents the maximum amount of money that can be robbed up to house i. We iterate through the list of houses and for each house, decide whether to rob it or skip it, based on the previous results stored in the dp table.
This solution defines a 'dp' array where each entry at index 'i' stores the maximum money that can be robbed from the first 'i+1' houses. At each house, you choose the maximum value between not robbing the current house or robbing it and adding its value to the maximum of all the previous non-adjacent houses.
Time Complexity: O(n) - We iterate through all houses once.
Space Complexity: O(n) - We use an additional array 'dp' to store intermediate results.
This approach optimizes the space complexity by not using a separate array for storing results of subproblems. Instead, we use two variables to keep track of the maximum amount that can be robbed up to the last two houses considered. This eliminates the need for an auxiliary array and reduces space complexity to O(1).
This C implementation contains no dp array but uses 'prev1' and 'prev2' variables to keep track of the maximum amounts robbed from the last house considered and the second last house, respectively. The current variable is updated each iteration.
Time Complexity: O(n) - Elements from the house array are each visited once.
Space Complexity: O(1) - Only a few extra variables are used for keeping track.
We design a function dfs(i), which represents the maximum amount of money that can be stolen starting from the i-th house. Thus, the answer is dfs(0).
The execution process of the function dfs(i) is as follows:
i \ge len(nums), it means all houses have been considered, and we directly return 0;i-th house, then dfs(i) = nums[i] + dfs(i+2); if not stealing from the i-th house, then dfs(i) = dfs(i+1).max(nums[i] + dfs(i+2), dfs(i+1)).To avoid repeated calculations, we use memoization search. The result of dfs(i) is saved in an array or hash table. Before each calculation, we first check if it has been calculated. If so, we directly return the result.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
We define f[i] as the maximum total amount that can be robbed from the first i houses, initially f[0]=0, f[1]=nums[0].
Consider the case where i \gt 1, the ith house has two options:
ith house, the total amount of robbery is f[i-1];ith house, the total amount of robbery is f[i-2]+nums[i-1];Therefore, we can get the state transition equation:
$
f[i]=
\begin{cases}
0, & i=0 \
nums[0], & i=1 \
max(f[i-1],f[i-2]+nums[i-1]), & i \gt 1
\end{cases}
The final answer is f[n], where n is the length of the array.
The time complexity is O(n), and the space complexity is O(n). Where n$ is the length of the array.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
We notice that when i \gt 2, f[i] is only related to f[i-1] and f[i-2]. Therefore, we can use two variables instead of an array to reduce the space complexity to O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Dynamic Programming - Iterative Approach | Time Complexity: O(n) - We iterate through all houses once. |
| Dynamic Programming - Optimized Space Approach | Time Complexity: O(n) - Elements from the house array are each visited once. |
| Memoization Search | — |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming - Iterative DP Array | O(n) | O(n) | Best for understanding the DP recurrence and explaining the transition clearly in interviews |
| Dynamic Programming - Optimized Space | O(n) | O(1) | Preferred in production or interviews when memory optimization is expected |
House Robber - Leetcode 198 - Python Dynamic Programming • NeetCode • 455,893 views views
Watch 9 more video solutions →Practice House Robber with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor