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 the amount of money in a house along a street. Adjacent houses cannot be robbed on the same night because of a security system. The goal is to compute the maximum amount of money you can steal without robbing two neighboring houses.
The constraint on adjacent houses immediately hints at a Dynamic Programming pattern. At each house you face a choice: rob it and skip the previous house, or skip it and keep the best value from the previous house. The optimal strategy emerges by evaluating these two choices repeatedly while iterating through the array.
Approach 1: Dynamic Programming - Iterative Array (O(n) time, O(n) space)
Create a DP array where dp[i] stores the maximum money you can rob from the first i + 1 houses. For each index, compute the best choice between skipping the current house (dp[i-1]) or robbing it (nums[i] + dp[i-2]). Iterate through the array once while filling this DP table. The transition becomes dp[i] = max(dp[i-1], nums[i] + dp[i-2]). This approach clearly expresses the recurrence relation and is often the easiest way to reason about the problem during interviews. Time complexity is O(n) because each house is processed once, and space complexity is O(n) for the DP array.
Approach 2: Dynamic Programming - Optimized Space (O(n) time, O(1) space)
The DP array stores more information than necessary. Each state only depends on the previous two results: the best value up to the previous house and the best value two houses back. Replace the DP array with two variables that track these values while iterating through the list. For every house, compute the new best value using current = max(prev1, prev2 + nums[i]), then shift the variables forward. This keeps the same recurrence but removes the extra memory. Time complexity remains O(n), while space complexity drops to O(1).
This pattern appears frequently in dynamic programming problems involving mutually exclusive choices across a sequence. Variants such as House Robber II and House Robber III build on the same idea but introduce circular streets or tree structures.
Recommended for interviews: Start with the DP array formulation to show the recurrence clearly: choose between robbing or skipping each house. Once the interviewer confirms the logic, reduce the memory to two variables. The optimized approach demonstrates stronger problem-solving maturity and awareness of 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming - Iterative Array | O(n) | O(n) | Best for explaining the recurrence clearly during interviews or learning dynamic programming |
| Dynamic Programming - Optimized Space | O(n) | O(1) | Preferred in production or interviews once the DP relation is understood and memory can be reduced |
DP 5. Maximum Sum of Non-Adjacent Elements | House Robber | 1-D | DP on Subsequences • take U forward • 505,828 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