# House Robber
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/house-robber)
Canonical: https://scaleengineer.com/dsa/problems/house-robber
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Zoho](https://scaleengineer.com/companies/zoho), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Turing](https://scaleengineer.com/companies/turing), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [Arcesium](https://scaleengineer.com/companies/arcesium), [Nordstrom](https://scaleengineer.com/companies/nordstrom), [CARS24](https://scaleengineer.com/companies/cars24), [Datadog](https://scaleengineer.com/companies/datadog), [Cleartrip](https://scaleengineer.com/companies/cleartrip)
---
## 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**_.

**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 <= 100`
* `0 <= nums[i] <= 400`

# Approaches
## Brute-Force Recursion
This approach directly models the decision-making process for each house using a recursive function. For each house, we explore two possibilities: either rob it and skip the next one, or skip it and move to the next one. This leads to exploring all possible valid combinations of robbing houses.
**Time:** O(2^n) · **Space:** O(n)
**Pros:** Simple to understand and implement, as it directly follows the problem's logic.
**Cons:** Extremely inefficient due to exponential time complexity.; Recalculates the same subproblems multiple times, leading to a 'Time Limit Exceeded' error on most platforms for larger inputs.
### Explanation
This method involves creating a recursive function that, for each house, calculates the maximum profit by considering two scenarios: robbing the current house or skipping it. If we rob the house at index `i`, we gain `nums[i]` and must skip the next house, so we recursively call the function for index `i + 2`. If we skip house `i`, we can move to the next house, so we recursively call for index `i + 1`. The function returns the maximum of these two outcomes. This process continues until we've considered all houses.

```java
class Solution {
    public int rob(int[] nums) {
        return robFrom(0, nums);
    }

    private int robFrom(int i, int[] nums) {
        // Base case: If we are past the last house, we can't rob anymore.
        if (i >= nums.length) {
            return 0;
        }

        // Option 1: Rob the current house (nums[i]) and skip the next one (i+1).
        int robCurrent = nums[i] + robFrom(i + 2, nums);

        // Option 2: Skip the current house and consider the next one (i+1).
        int skipCurrent = robFrom(i + 1, nums);

        // Return the maximum of the two options.
        return Math.max(robCurrent, skipCurrent);
    }
}
```
The main drawback is its performance. The number of recursive calls grows exponentially with the number of houses, as the function repeatedly solves the same subproblems. For an input array of size `n`, the time complexity is O(2^n).
### Algorithm
- Create a recursive function, say `robFrom(index, nums)`.
- The base case for the recursion is when `index` is out of bounds of the `nums` array (i.e., `index >= nums.length`). In this case, return 0 as no more houses can be robbed.
- In the recursive step, for the current house at `index`, there are two choices:
    1. Rob the current house: The profit is `nums[index]` plus the result of a recursive call starting from `index + 2` (since the next house cannot be robbed).
    2. Skip the current house: The profit is the result of a recursive call starting from `index + 1`.
- Return the maximum of these two choices.
- The initial call to the function will be `robFrom(0, nums)`.

## Dynamic Programming with Memoization (Top-Down)
This approach improves upon the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We use an array (or a hash map) to store the results of subproblems once they are calculated. When the function is called again with the same input, it returns the stored result instead of re-calculating it.
**Time:** O(n) · **Space:** O(n)
**Pros:** Significantly more efficient than brute-force.; Guarantees that each subproblem is solved only once.; Maintains the recursive structure which can be intuitive.
**Cons:** Uses O(n) extra space for the memoization table and recursion stack.; Can lead to stack overflow for very large `n` if the recursion depth is too high (though not an issue with the given constraints).
### Explanation
To optimize the brute-force approach, we can store the results of subproblems in a memoization table (an array in this case). This technique is a form of top-down dynamic programming. We create a `memo` array, where `memo[i]` will store the maximum amount of money that can be robbed from house `i` to the end of the street.

Before making the recursive calls to compute the result for index `i`, we first check if `memo[i]` has already been computed. If it has, we simply return the stored value. Otherwise, we perform the computation, store the result in `memo[i]`, and then return it. This ensures that each subproblem is solved only once.

```java
import java.util.Arrays;

class Solution {
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1); // Initialize memo table with -1
        return robFrom(0, nums);
    }

    private int robFrom(int i, int[] nums) {
        if (i >= nums.length) {
            return 0;
        }
        // If we have already solved this subproblem, return the stored result.
        if (memo[i] != -1) {
            return memo[i];
        }

        // Rob current house + max from house i+2 onwards
        int robCurrent = nums[i] + robFrom(i + 2, nums);
        // Skip current house, get max from house i+1 onwards
        int skipCurrent = robFrom(i + 1, nums);

        // Store the result in the memo table and return it.
        memo[i] = Math.max(robCurrent, skipCurrent);
        return memo[i];
    }
}
```
This optimization drastically reduces the time complexity from exponential to linear, O(n), because each state `robFrom(i, ...)` is computed at most once. The space complexity is O(n) to store the memoization table and for the recursion call stack.
### Algorithm
- Create a memoization array, `memo`, of the same size as `nums`, initialized with a value indicating that the state has not been computed (e.g., -1).
- Create a recursive helper function, `robFrom(index, nums, memo)`.
- The base case is the same: if `index` is out of bounds, return 0.
- Before computing, check if `memo[index]` has been calculated. If so, return `memo[index]`.
- If not, calculate the result using the same recurrence as the brute-force approach: `max(nums[index] + robFrom(index + 2, ...), robFrom(index + 1, ...))`.
- Store this result in `memo[index]` before returning it.
- The initial call will be `robFrom(0, nums, memo)`.

## Iterative Dynamic Programming with an Array
This approach uses a bottom-up dynamic programming strategy. We build a DP array, where `dp[i]` represents the maximum amount of money that can be robbed up to house `i`. We iterate through the houses and calculate `dp[i]` based on the values for previous houses, effectively building the solution from the smallest subproblem to the final answer.
**Time:** O(n) · **Space:** O(n)
**Pros:** Efficient with linear time complexity.; Avoids recursion, so no risk of stack overflow.; Generally slightly faster than memoization due to no recursion overhead.
**Cons:** Uses O(n) extra space for the DP array, which can be optimized.
### Explanation
Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. We define a `dp` array where `dp[i]` stores the maximum amount of money that can be robbed from the first `i+1` houses (i.e., from house 0 to house `i`).

The state transition is based on the same decision at each house `i`:
1.  Don't rob house `i`: The max profit is the same as the max profit up to house `i-1`, which is `dp[i-1]`.
2.  Rob house `i`: The max profit is `nums[i]` plus the max profit up to house `i-2` (since we can't rob `i-1`), which is `nums[i] + dp[i-2]`.

So, the recurrence relation is `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`.

We handle the base cases for the first one or two houses and then iterate through the rest of the array to fill the `dp` table. The final answer is the value at the last index of the `dp` array.

```java
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        
        // Base cases
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        // Fill the rest of the dp table
        for (int i = 2; i < nums.length; i++) {
            // dp[i-1] -> Don't rob house i
            // nums[i] + dp[i-2] -> Rob house i
            dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
        }

        return dp[nums.length - 1];
    }
}
```
This approach has a time complexity of O(n) and a space complexity of O(n) for the DP array. It avoids recursion, thus eliminating the risk of stack overflow and the overhead associated with function calls.
### Algorithm
- Handle edge cases: if `nums` is empty, return 0; if it has one element, return that element.
- Create a DP array, `dp`, of the same size as `nums`.
- Initialize the base cases:
    - `dp[0] = nums[0]`
    - `dp[1] = max(nums[0], nums[1])`
- Iterate from `i = 2` to `nums.length - 1`.
- In each iteration, apply the recurrence relation: `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`.
    - `dp[i-1]` represents the choice of not robbing house `i`.
    - `dp[i-2] + nums[i]` represents the choice of robbing house `i`.
- The final answer is the last element of the `dp` array, `dp[nums.length - 1]`.

## Space-Optimized Iterative Dynamic Programming
This is the most efficient approach. It builds upon the iterative DP solution by noticing that the calculation for the current house `i` only depends on the results for the previous two houses (`i-1` and `i-2`). Therefore, we don't need to store the entire DP array. We can use just two variables to keep track of the necessary previous results, reducing the space complexity to constant.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal solution with linear time and constant space complexity.; Very efficient and practical for large inputs.
**Cons:** The logic can be slightly less intuitive to grasp initially compared to the direct DP array approach.
### Explanation
We can optimize the space complexity of the iterative DP approach. Observing the recurrence relation `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`, we see that to compute the maximum profit for the current house, we only need the results from the previous two houses. This means we don't need to maintain the entire `dp` array.

We can use two variables to track the required information. Let's use `rob1` to store the maximum profit up to the previous house (`dp[i-1]`) and `rob2` to store the maximum profit up to the house before that (`dp[i-2]`).

As we iterate through the houses, we calculate the current maximum profit, `current_max = max(rob1, rob2 + nums[i])`. Then, for the next iteration, the previous `rob1` becomes the new `rob2`, and `current_max` becomes the new `rob1`.

```java
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int rob1 = 0; // Represents the max profit ending at the previous house (dp[i-1])
        int rob2 = 0; // Represents the max profit ending at the house before previous (dp[i-2])

        // [rob2, rob1, num, num+1, ...]
        for (int num : nums) {
            // The new max profit is either robbing the current house (num + rob2)
            // or not robbing it (rob1).
            int temp = Math.max(num + rob2, rob1);
            
            // Update pointers for the next iteration
            rob2 = rob1;
            rob1 = temp;
        }

        return rob1;
    }
}
```
This optimized solution maintains the O(n) time complexity but reduces the space complexity to O(1), making it the most efficient approach.
### Algorithm
- Initialize two variables, `rob1 = 0` and `rob2 = 0`. `rob1` will store the maximum profit ending at the previous house considered, and `rob2` will store the maximum profit ending at the house before that.
- Iterate through each amount `num` in the `nums` array.
- In each iteration, calculate the maximum profit if we consider the current house `num`. This would be `max(num + rob2, rob1)`.
    - `num + rob2`: Rob the current house (`num`) plus the max profit from two houses ago (`rob2`).
    - `rob1`: Don't rob the current house, so the max profit is the same as the max profit from the previous house (`rob1`).
- Store this new maximum in a temporary variable, say `temp`.
- Update `rob2` to be the old `rob1`.
- Update `rob1` to be `temp`.
- After iterating through all the houses, `rob1` will hold the maximum possible profit. Return `rob1`.

# Solutions
### JavaScript

```javascript
function rob ( nums ) { const n = nums . length ; const f = Array ( n ). fill ( - 1 ); const dfs = i => { if ( i >= n ) { return 0 ; } if ( f [ i ] < 0 ) { f [ i ] = Math . max ( nums [ i ] + dfs ( i + 2 ), dfs ( i + 1 )); } return f [ i ]; }; return dfs ( 0 ); }
```

### Python

```python
# greedy class Solution : def rob ( self , nums : List [ int ]) -> int : not_rob , rob = 0 , nums [ 0 ] for num in nums [ 1 :]: # must max check # eg. first robbed 99999, then following ones are just 3,3,3,3,3 not_rob , rob = rob , max ( num + not_rob , rob ) return rob ############ class Solution ( object ): def rob ( self , nums ): """ :type nums: List[int] :rtype: int """ if len ( nums ) == 0 : return 0 if len ( nums ) <= 2 : return max ( nums ) dp = [ 0 for i in range ( 0 , 2 )] dp [ 0 ] = nums [ 0 ] dp [ 1 ] = max ( nums [ 1 ], nums [ 0 ]) for i in range ( 2 , len ( nums )): dp [ i % 2 ] = max ( dp [( i - 1 ) % 2 ], dp [( i - 2 ) % 2 ] + nums [ i ]) return dp [( len ( nums ) - 1 ) % 2 ]
```

### Java

```java
public class House_Robber { class Solution { public int rob ( int [] nums ) { if ( nums == null || nums . length == 0 ) { return 0 ; } // dp[i] means until i, max possible amount int [] dp = new int [ nums . length + 1 ]; dp [ 0 ] = 0 ; dp [ 1 ] = nums [ 0 ]; for ( int i = 2 ; i <= nums . length ; i ++) { // 2 cases: rob current house, not rob current dp [ i ] = Math . max ( nums [ i - 1 ] + dp [ i - 2 ], dp [ i - 1 ]); } return dp [ nums . length ]; } } } ///////// class Solution { public int rob ( int [] nums ) { int a = 0 , b = nums [ 0 ]; for ( int i = 1 ; i < nums . length ; ++ i ) { int c = Math . max ( nums [ i ] + a , b ); a = b ; b = c ; } return b ; } }
```

### CPP

```cpp
// rob[i + 1] = nums[i] + skip[i] // If we rob at house[i], we must skip house[i-1] // skip[i + 1] = max(rob[i - 1], skip[i - 1]) // If we skip house[i], we can pick the maximum from robbing or skipping house[i-1] class Solution { public: int rob ( vector < int >& nums ) { int n = nums . size (); int a = 0 , b = nums [ 0 ]; for ( int i = 1 ; i < n ; ++ i ) { int c = max ( nums [ i ] + a , b ); a = b ; b = c ; } return b ; } };
```