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]))

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment