House Robber — Day 18(Python)

Image for post
Image for post
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:

Example 2:

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

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.

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.

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.

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