Solution 1

  • TimeO(n)
  • SpaceO(n)

Where, n is number of houses.

Simple DFS with memoization problem. But the most optimal solution is below, has O(1) space complexity.

Python
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(n)
    Where, n is number of houses.

    Simple DFS with memoization problem. But the most optimal solution is below, 
    has O(1) space complexity.
    '''
    def rob(self, nums: List[int]) -> int:
        cache = {}

        def dfs(i):
            if i in cache:
                return cache[i]
            if i >= len(nums):
                return 0
            res = max(nums[i] + dfs(i+2), dfs(i+1))
            cache[i] = res
            return res
        
        return dfs(0)
Leet Code/python.py · L2763–2785

Solution 2

  • TimeO(n)
  • SpaceO(1)

Where, n is number of houses.
This is the most optimal solution with O(1) space complexity.

Python
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(1)
    Where, n is number of houses.
    This is the most optimal solution with O(1) space complexity.
    '''
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

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

        return rob2
Leet Code/python.py · L2787–2803