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] <= 400The House Robber problem is a classic dynamic programming challenge involving decision making at each step. You are given an array where each element represents the amount of money in a house, and you cannot rob two adjacent houses. The key idea is to determine the maximum money you can collect without violating this constraint.
At each house, you have two choices: rob the current house and add its value to the best result from two houses back, or skip the current house and keep the maximum value from the previous house. By comparing these two options, you build an optimal solution step by step.
This leads to a recurrence relation that can be solved using a DP array or optimized to use just two variables representing previous states. The approach processes the array once, giving O(n) time complexity, while space can be reduced to O(1) with state optimization.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (DP Array) | O(n) | O(n) |
| Optimized DP (Two Variables) | O(n) | O(1) |
take U forward
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.
Time Complexity: O(n) - We iterate through all houses once.
Space Complexity: O(n) - We use an additional array 'dp' to store intermediate results.
1function rob(nums) {
2 if (nums.length === 0) return 0;
3 if (nums.length === 1)
JavaScript implementation where an array 'dp' tracks the amount that can be maximally robbed up to each house index. The decision at each array position is made to either include it in the profit or skip it, depending on which yields a greater sum.
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).
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, House Robber is a common interview question at FAANG and other top tech companies. It tests a candidate’s understanding of dynamic programming, state transitions, and optimization techniques.
The optimal approach uses dynamic programming. At each house, you decide whether to rob it and add the value from two houses before, or skip it and keep the previous maximum. This ensures you compute the best possible loot while avoiding adjacent houses.
An array or simple variables are typically used to store dynamic programming states. A DP array tracks the best profit up to each house, while an optimized solution only keeps the last two computed values to reduce space.
The problem exhibits overlapping subproblems and optimal substructure. The maximum loot for a given house depends on previously computed results, making it ideal for building a solution using dynamic programming.
In this Java solution, prev1 and prev2 manage houses up to the current house being considered, replacing the function of a dp array with sequence variables and logic to determine inclusion.