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

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Dependency Injection with Factory

My Favorite Medium Publications For Python Programmers

Run Core Haptics on a PS5 Controller

Learning gRPC with an Example

This Package Converts Jupyter Notebooks To Code

A Musical Tour of Hints and Tools for Debugging Host Networks

How to write generic dissectors in Wireshark

| Engineering News-Record

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

More from Medium

Solution to the k-closest point in space problem

Minimum Spanning Tree & Prim’s Algorithm

LeetCode Ranking 562,030 (April 28)

Graph Algorithm — Cycle Detection in Directed Graph using DFS