House Robber Leetcode Problem 198 [Python Solution]

House Robber Leetcode problem is a 1-D Dynamic Programming category problem and is considered of medium difficulty.

We will walk through the problem, provide a detailed solution in Python, discuss its time and space complexity, and explain the reasoning behind our approach.

Problem Overview

You are a professional robber planning to rob houses along a street.

Each house has a certain amount of money stashed, but there’s a constraint that prevents you from robbing adjacent houses on the same night.

If two adjacent houses are broken into, they will trigger a security system that contacts the police.

Given an integer array nums representing the amount of money in each house, your task is to 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).

The total amount you can rob is 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).

The total amount you can rob is 2 + 9 + 1 = 12.

Constraints:

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

Efficient Python Code Solution

Now, let’s provide an efficient Python solution to this problem using dynamic programming:

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2 

In this solution, we use two variables, rob1 and rob2, to keep track of the maximum amount we can rob up to the current house.

We initialize both variables to 0, as if there are no houses, we can’t rob anything.

We then iterate through the nums array, considering each house one by one.

For each house, we calculate two potential options:

1. Rob the current house (n) and add its value to the amount robbed from the house two positions back (rob1).

This option represents robbing the current house and the house before the previous one.

2. Skip the current house and keep the value from the previous house (rob2).

This option represents not robbing the current house.

We take the maximum of these two options and update temp with it.

Then, we update rob1 with the previous value of rob2, and rob2 with the value of temp.

After iterating through all the houses, rob2 will hold the maximum amount that can be robbed from the neighborhood while satisfying the constraint of not robbing adjacent houses.

This value is then returned as the final result.

Time and Space Complexity

Let’s analyze the time and space complexity of our solution:

• Time Complexity: The time complexity is O(n), where n is the number of houses.

We iterate through the nums array once.

• Space Complexity: The space complexity is O(1).

We use a constant amount of extra space for our two variables, rob1 and rob2, regardless of the input size.

Reasoning Behind Our Approach

The key to solving this problem efficiently lies in recognizing that we can break it down into smaller subproblems.

At each house, we have two choices: either rob it or skip it.

The maximum amount we can rob up to the current house depends on the decisions made in the previous houses.

By keeping track of the maximum amount we can rob at each step, we can compute the final solution without the need for an extensive decision tree or recursion.

Related Interview Questions By Company:

• Hand Of Straights LeetCode
• Word Break LeetCode
• Jump Game II LeetCode

Related Interview Questions By Difficulty:

• Palindromic Substrings LeetCode
• Partition Equal Subset Sum LeetCode
• Number Of Longest Increasing Subsequence LeetCode

Related Interview Questions By Category:

• Insert Into A Binary Search Tree LeetCode
• Clone Graph LeetCode
• Minimum Interval To Include Each Query LeetCode

Conclusion

In this guide, we’ve addressed the LeetCode problem 198, House Robber We’ve provided a Python solution that efficiently calculates the maximum amount of money you can rob from a neighborhood of houses without robbing adjacent ones.

This problem is an excellent introduction to dynamic programming and serves as the foundation for solving more complex problems in this category.

If you found this guide helpful, please consider leaving a like and subscribing to our content.

If you have any questions, suggestions, or need further clarification, don’t hesitate to comment below.

Understanding this problem will not only help you master dynamic programming but also prepare you for more challenging coding interviews and competitive programming tasks.

Happy coding!

Question Link

Feel free to comment, ask questions, make suggestions, and share this content with others who may find it valuable.