Q93: House Robber (I & II). - DSA Patterns (Multi-Lang)

In Simple Words:

House Robber I: rob = max(rob1 + n, rob2).
House Robber II (Circular): First and last houses are neighbors. Run House Robber I twice: on nums[1:] (excluding first) and nums[:-1] (excluding last).
Time: $O(N)$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def rob(nums: list[int]) -> int:
    rob1, rob2 = 0, 0
    for n in nums:
        new_rob = max(rob1 + n, rob2)
        rob1 = rob2
        rob2 = new_rob
    return rob2

def robII(nums: list[int]) -> int:
    if len(nums) == 1: return nums[0]
    return max(rob(nums[1:]), rob(nums[:-1]))