LeetCode 213: House Robber Ii — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Dynamic Programming | Array | House Robber

The Problem

Find the maximum amount of money you can rob from houses arranged in a circle, where you cannot rob two adjacent houses and the first and last houses are neighbors.

Approach

Since houses form a circle, we cannot rob both the first and last house. We solve this by running the linear House Robber algorithm twice: once excluding the first house, and once excluding the last house, then taking the maximum result.

Time: O(n) · Space: O(1)

Code

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

            prev = 0
            curr = 0

            for num in nums:
                temp = curr
                curr = max(prev + num, curr)
                prev = temp

            return curr

        if len(nums) == 1:
            return nums[0]

        # Rob first house and exclude the last house, or exclude the first house and rob the last house.
        return max(houseRobber(nums[1:]), houseRobber(nums[:-1]))