Daily Problem: LC 213 House Robber II

Solution with comments in python3

class Solution:
def house_rob(self, nums):
if not nums:return 0
if len(nums) <=2:return max(nums)
rob, not_rob = 0, 0
ret = 0
for num in nums:
# not rob at this num will be: max( rob + 0, not_rob)
# 0 means not rob at this num
new_not_rob = max(rob, not_rob)
# new_rob will be old not rob + num
new_rob = not_rob + num
rob, not_rob = new_rob, new_not_rob
ret = max(ret, not_rob, rob )
return ret
def rob(self, nums: List[int]) -> int:
if len(nums) <=2: return max(nums)
# we can not rob the first and the last at the same time. So the
# problem is change to either rob the 0 to n-2 inclusively
# or 1 to n-1 inclusively.
return max(self.house_rob(nums[:-1]), self.house_rob(nums[1:]))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi