House Robber — Day 18(Python)

Photo by Luis Villasmil on Unsplash

Today we will learn how to rob houses, not literally, house robber one of the frequent coding questions in a technical coding interview. Let us see how to solve the problem.

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

We are supposed to rob houses such that we earn maximum profit. One constraint to keep in mind before robbing houses is to ensure that we don’t rob houses that are next to each other else we would alert the police.

Let us consider a few examples.

Input: nums = [2]
Output: 2
Explanation: Since we have one house, Rob house1 (money = 2).
Input: nums = [2, 5]
Output: 5
Explanation: Since we have two houses, Rob max of house1 and house2.
Max is house2 (money = 5). The total amount you can rob is 5.
Input: nums = [2, 5, 4]
Output: 6
Explanation: We have three houses, Rob either house1 and house3, or house2. house1 + house3(money = 2 + 4 = 6) or house2(money = 5).
Rob house1 and house3. The total amount you can rob is 5.

One thing to notice from the above examples is, we have to take into consideration the amount in the current house, the total amount in the house before as well as the total amount in the house before to the prior house. We can use a list that can give us the maximum profit obtained in a particular house number. To find the maximum amount, find the amount at the end of the list. Let us look into the code snippet.

class Robber:
def rob(self, nums: List[int]) -> int:
if(len(nums) == 0):
return 0
if(len(nums) == 1):
return nums[0]
if(len(nums) == 2):
return max(nums[0], nums[1])
dp = [0 for row in range(len(nums))]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max((nums[i] + dp[i - 2]),dp[i-1])
return dp[-1]

Complexity analysis

Time Complexity

We need to traverse through the entire list once while finding the solution, and, hence time complexity is O(N).

Space Complexity

We are creating an array of sizes the same as the given array size, and, hence space complexity is O(N).

Can we try to optimize the space complexity? We care about profit in the previous two houses. How about instead of keeping the entire list, we make use of 2 variables? Let us look into the code snippet.

class Robber:
def rob(self, nums: List[int]) -> int:
if(len(nums) == 0):
return 0
if(len(nums) == 1):
return nums[0]
if(len(nums) == 2):
return max(nums[0], nums[1])
house_before_before = nums[0]
house_before = max(nums[0], nums[1])
house_current = 0
for i in range(2, len(nums)):
house_current = max((nums[i] + house_before_before),house_before)
house_before_before = house_before
house_before = house_current
return house_current

Complexity analysis

Time Complexity

We need to traverse through the entire list once while finding the solution, and, hence time complexity is O(N).

Space Complexity

We are creating two variables to store the profit in the previous two houses, and, hence time complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

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