Friedrich Ewald My Personal Website

Leetcode: House robber

Given an array of nums that represent the loot of a house robber, return the maximum amount of money a robber can steal. The only rule is that a robber can not steal from two neighboring houses. When looking at this problem, we can see that we want to maximize the number of houses that we rob from. Consider the following array: [0,1,0,1]. Our maximum profit is 2, because we can rob the house at index 1 and index 3. If we were to rob at index 0 and 2, we would only gain 0 profit. We cannot however simply compare the even versus the odd indices because there could also be the following situation: [10,5,5,10]. Here, it is advantageous to skip 2 instead of just skipping 1. We need to look at every step if we want to visit the one after the next or the one after this. We don’t need to look if we want to visit the one after this, because then we could also simply have visited the one after the next. Generally speaking, we always need to look at the index+2 and at the index+3. To solve this problem, we can look backwards at the array. At position 0, we can only rob 0. At position 1 we can only rob 1. At position 2 we can rob 0 and 2. From there on, we can iterate over the array and calculate the maximum for each position and add the current loot. Finally, we can return the maximum of the two last positions of the array.

from typing import List

class Solution:
  def rob(self, nums: List[int]) -> int:
    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] = m[0] + nums[2]
    for pos in range(3, len(nums)):
      m[pos] = max(m[pos-2], m[pos-3]) + nums[pos]
    return max(m[-1], m[-2])

if __name__ == '__main__':
  s = Solution().rob
  print(s([1,2,1,1]), 3)
Runtime: 39 ms, faster than 80.95% of Python3 online submissions for House Robber. Memory Usage: 14 MB, less than 19.55% of Python3 online submissions for House Robber.

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.