198. House Robber - Explanation

Description

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a straight line, i.e. the ith house is the neighbor of the (i-1)th and (i+1)th house.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

Example 1:

Input: nums = [1,1,3,3]

Output: 4

Explanation: nums[0] + nums[2] = 1 + 3 = 4.

Example 2:

Input: nums = [2,9,8,3,6]

Output: 16

Explanation: nums[0] + nums[2] + nums[4] = 2 + 8 + 6 = 16.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Topics

Array Dynamic Programming

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of houses.

Hint 1

Can you think of this problem in terms of recursion? Consider drawing a decision tree where, at each step, we can choose to rob the house or skip it. If we rob the current house, we cannot rob the next or the previous house. Can you derive a recurrence relation to solve the problem?

Hint 2

We can recursively start from the first house and branch paths accordingly. If we rob the current house, we skip the next house; otherwise, we move to the next house. The recurrence relation can be expressed as max(nums[i] + dfs(i + 2), dfs(i + 1)), where i is the current house and dfs is the recursive function. Can you determine the base condition to stop the recursion?

Hint 3

The base condition would be to return 0 when i goes out of bounds. This recursion can leads to O(2^n) time solution. Can you think of a better way? Maybe you should try to avoid recalculating the result for a recursive call.

Hint 4

We can use Memoization to avoid recalculating the result multiple times for a recursive call. By storing the result of each recursive call in a hash map or an array using i as the parameter, we can immediately return the stored result if the recursion is called with the same i value again. Further optimization can be achieved using advanced techniques like Bottom-Up dynamic programming.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming Fundamentals - Understanding optimal substructure and overlapping subproblems
Recursion - Breaking down problems into smaller subproblems
Memoization - Caching computed results to avoid redundant calculations
Array Traversal - Iterating through elements while maintaining state

1. Recursion

Intuition

At every house, you have two choices:

Skip the current house → move to the next house.
Rob the current house → take its money and skip the next house.

The goal is to choose the option that gives the maximum total money.
Recursion tries both choices at each index and returns the best result.

Algorithm

Start from house 0.
For each index i:
- Option 1: Skip the house → solve for i + 1
- Option 2: Rob the house → nums[i] + solve(i + 2)
Return the maximum of the two options.
If i goes out of bounds, return 0.

class Solution:
    def rob(self, nums: List[int]) -> int:

        def dfs(i):
            if i >= len(nums):
                return 0
            return max(dfs(i + 1),
                       nums[i] + dfs(i + 2))

        return dfs(0)

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

    private int dfs(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        return Math.max(dfs(nums, i + 1),
                        nums[i] + dfs(nums, i + 2));
    }
}

class Solution {
public:
    int rob(vector<int>& nums) {
        return dfs(nums, 0);
    }

    int dfs(vector<int>& nums, int i) {
        if (i >= nums.size()) {
            return 0;
        }
        return max(dfs(nums, i + 1),
                   nums[i] + dfs(nums, i + 2));
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        const dfs = (i) => {
            if (i >= nums.length) {
                return 0;
            }
            return Math.max(dfs(i + 1), nums[i] + dfs(i + 2));
        };
        return dfs(0);
    }
}

public class Solution {
    public int Rob(int[] nums) {
        return Dfs(nums, 0);
    }

    private int Dfs(int[] nums, int i) {
        if (i >= nums.Length) {
            return 0;
        }
        return Math.Max(Dfs(nums, i + 1),
               nums[i] + Dfs(nums, i + 2));
    }
}

class Solution {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        fun dfs(i: Int): Int {
            if (i >= n) return 0
            return maxOf(dfs(i + 1), nums[i] + dfs(i + 2))
        }
        return dfs(0)
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        func dfs(_ i: Int) -> Int {
            if i >= nums.count {
                return 0
            }
            return max(dfs(i + 1), nums[i] + dfs(i + 2))
        }

        return dfs(0)
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same subproblems many times.
To optimize this, we store the result for each index once it’s computed.

At every house i, you still have two choices:

Skip the house → go to i + 1
Rob the house → take nums[i] and go to i + 2

Using memoization, each index is solved only once.

Algorithm

Create a memo array where memo[i] stores the maximum money from house i.
Define a recursive function dfs(i):
- If i is out of bounds, return 0.
- If memo[i] is already computed, return it.
- Compute:
  - skip = dfs(i + 1)
  - rob = nums[i] + dfs(i + 2)
- Store and return max(skip, rob) in memo[i].
Start recursion from index 0.

class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = [-1] * len(nums)

        def dfs(i):
            if i >= len(nums):
                return 0
            if memo[i] != -1:
                return memo[i]
            memo[i] = max(dfs(i + 1), nums[i] + dfs(i + 2))
            return memo[i]

        return dfs(0)

public class Solution {
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return dfs(nums, 0);
    }

    private int dfs(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = Math.max(dfs(nums, i + 1),
                         nums[i] + dfs(nums, i + 2));
        return memo[i];
    }
}

class Solution {
public:
    vector<int> memo;

    int rob(vector<int>& nums) {
        memo.resize(nums.size(), -1);
        return dfs(nums, 0);
    }

    int dfs(vector<int>& nums, int i) {
        if (i >= nums.size()) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = max(dfs(nums, i + 1),
                    nums[i] + dfs(nums, i + 2));
        return memo[i];
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        const memo = new Int32Array(nums.length).fill(-1);
        const dfs = (i) => {
            if (i >= nums.length) {
                return 0;
            }
            if (memo[i] !== -1) {
                return memo[i];
            }
            return (memo[i] = Math.max(dfs(i + 1), nums[i] + dfs(i + 2)));
        };
        return dfs(0);
    }
}

public class Solution {
    private int[] memo;

    public int Rob(int[] nums) {
        memo = new int[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            memo[i] = -1;
        }
        return Dfs(nums, 0);
    }

    private int Dfs(int[] nums, int i) {
        if (i >= nums.Length) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = Math.Max(Dfs(nums, i + 1),
                         nums[i] + Dfs(nums, i + 2));
        return memo[i];
    }
}

class Solution {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        var memo = IntArray(n+1){-1}
        fun dfs(i: Int): Int {
            if (i >= n) return 0
            if (memo[i] != -1) return memo[i]
            memo[i] = maxOf(dfs(i + 1), nums[i] + dfs(i + 2))
            return memo[i]
        }
        return dfs(0)
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var memo = Array(repeating: -1, count: nums.count)

        func dfs(_ i: Int) -> Int {
            if i >= nums.count {
                return 0
            }
            if memo[i] != -1 {
                return memo[i]
            }
            memo[i] = max(dfs(i + 1), nums[i] + dfs(i + 2))
            return memo[i]
        }

        return dfs(0)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of deciding recursively, we build the answer step by step.

For each house i, the maximum money we can have depends on:

Not robbing it → same money as i - 1
Robbing it → money at i + best up to i - 2

We choose the better of the two at every step.

Algorithm

Handle edge cases:
- No houses → return 0
- One house → return its value
Create a DP array where dp[i] = max money up to house i.
Initialize:
- dp[0] = nums[0]
- dp[1] = max(nums[0], nums[1])
For each house i from 2 to n - 1:
- dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
Return dp[n - 1].

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])

        return dp[-1]

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

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

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.length - 1];
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        if (nums.length === 0) return 0;
        if (nums.length === 1) return nums[0];

        const dp = new Array(nums.length).fill(0);
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (let i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.length - 1];
    }
}

public class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];

        int[] dp = new int[nums.Length];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);

        for (int i = 2; i < nums.Length; i++) {
            dp[i] = Math.Max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.Length - 1];
    }
}

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.isEmpty()) {
            return 0
        }
        if (nums.size == 1) {
            return nums[0]
        }

        val dp = IntArray(nums.size)
        dp[0] = nums[0]
        dp[1] = maxOf(nums[0], nums[1])

        for (i in 2 until nums.size) {
            dp[i] = maxOf(dp[i - 1], nums[i] + dp[i - 2])
        }

        return dp[nums.size - 1]
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        if nums.count == 1 {
            return nums[0]
        }

        var dp = Array(repeating: 0, count: nums.count)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in 2..<nums.count {
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
        }

        return dp[nums.count - 1]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized)

Intuition

We don’t actually need a full DP array.

At any house, we only care about:

the best result up to the previous house
the best result up to the house before that

So instead of storing everything, we just keep two variables and update them as we move forward.

For each house:

Either skip it → keep previous best
Or rob it → current money + best from two steps back
Pick the maximum.

Algorithm

Initialize two variables:
- rob1 → best up to house i - 2
- rob2 → best up to house i - 1
For each house value:
- Compute newRob = max(rob2, rob1 + currentHouseValue)
- Move pointers:
  - rob1 = rob2
  - rob2 = newRob
After processing all houses, rob2 is the answer.

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for num in nums:
            temp = max(num + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2

public class Solution {
    public int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;

        for (int num : nums) {
            int temp = Math.max(num + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
}

class Solution {
public:
    int rob(vector<int>& nums) {
        int rob1 = 0, rob2 = 0;

        for (int num : nums) {
            int temp = max(num + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    rob(nums) {
        let rob1 = 0;
        let rob2 = 0;

        for (const num of nums) {
            const temp = Math.max(num + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
}

public class Solution {
    public int Rob(int[] nums) {
        int rob1 = 0, rob2 = 0;

        foreach (int num in nums) {
            int temp = Math.Max(num + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
}

func rob(nums []int) int {
    rob1, rob2 := 0, 0
    for _, num := range nums {
        temp := max(num+rob1, rob2)
        rob1 = rob2
        rob2 = temp
    }
    return rob2
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun rob(nums: IntArray): Int {
        var rob1 = 0
        var rob2 = 0
        for (num in nums) {
            val temp = maxOf(num + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        }
        return rob2
    }
}

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var rob1 = 0, rob2 = 0

        for num in nums {
            let temp = max(num + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        }

        return rob2
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Incorrect Base Case Initialization

In the bottom-up DP approach, dp[1] should be initialized as max(nums[0], nums[1]), not just nums[1]. This represents the maximum money obtainable from the first two houses. If you set dp[1] = nums[1], you ignore the possibility that the first house might have more money, leading to suboptimal results.

Confusing the Recurrence Relation

The recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]) represents choosing between skipping house i (keeping the best from i-1) or robbing house i (adding its value to the best from i-2). A common mistake is writing dp[i] = max(dp[i-1] + nums[i], dp[i-2]), which incorrectly adds the current house value when skipping it. Remember: robbing requires jumping over the previous house, not adding to it.

Not Handling Edge Cases for Empty or Single-Element Arrays

When the input array is empty, return 0. When it has only one element, return that element. The bottom-up approach with a DP array requires at least two elements to initialize dp[0] and dp[1]. Failing to handle these edge cases causes index-out-of-bounds errors or incorrect results. The space-optimized solution with two variables naturally handles the single-element case but still needs an empty array check.