Framework Thinking - Neetcode 150 - House Robber

Here is solutions for House Robber.

1. Understand the problem

2. Clarify constraints, asks 4 - 5 questions including edge cases.

3. Explore examples.

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

5. Implement solutions.

5.1. Recursion - Time O(2^N), Space O(N)

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)

  • Time: O(2^N)

  • Space O(N)

5.2. Dynamic Programming (Top-Down) - Time O(N), Space O(N)

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)

  • Time: O(N)

  • Space O(N)

5.3. Dynamic Programming (Bottom-Up) - Time O(N), Space O(N)

  • dp[i]: maximum value can get from rob at the house[i].
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]

  • Time: O(N)

  • Space O(N)

5.4.Dynamic Programming (Space Optimized) - Time O(N), Space 0(1)

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

  • Time: O(N)

  • Space O(1)

6. Dry run testcases.

December 7, 2025