Friedrich Ewald My Personal Website

Leetcode: House robber II

Similar to “House Robber”, but now we have to assume that the houses are aligned in a circle and the last house is a neighbor of the first house. We can solve it similarly but remove the first and last element and take the maximum of the result.

class Solution:
  def rob(self, nums: List[int]) -> int:
    if len(nums) < 2:
      return nums[0]
    return max(self.r(nums[:-1]), self.r(nums[1:]))

  def r(self, nums):
      if len(nums) < 2:
        return nums[0]
      if len(nums) < 3:
        return max(nums[0], nums[1])
      m = [0 for _ in nums]
      m[0] = nums[0]
      m[1] = nums[1]
      m[2] = max(m[0]+nums[2], m[1])
      for pos in range(3, len(nums)):
        m[pos] = max(m[pos-2], m[pos-3]) + nums[pos]
      return max(m[-1], m[-2])
Runtime: 63 ms, faster than 22.78% of Python3 online submissions for House Robber II. Memory Usage: 13.9 MB, less than 70.83% of Python3 online submissions for House Robber II.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.