House Robber#

Difficulty: Medium

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Constraints:

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 400

Probelm Explanation:#

The problem is a classic dynamic programming challenge known as the “House Robber” problem. The scenario is that you are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, but the constraint is that adjacent houses have security systems connected. If two adjacent houses are broken into on the same night, the security systems will automatically contact the police.

The goal is to determine the maximum amount of money you can rob tonight without alerting the police. You need to find a strategy to maximize your earnings while avoiding robbing two adjacent houses.

The input to the problem is an array nums, where nums[i] represents the amount of money in the i-th house. The task is to return the maximum amount of money that can be robbed without triggering the security system.

For example:

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.

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.

The challenge involves designing an algorithm to efficiently solve this problem and find the optimal strategy for robbing houses to maximize the stolen money while adhering to the constraint of not robbing adjacent houses. The provided solution utilizes dynamic programming to achieve this.

Solution:#

Here’s a Python function to implement this algorithm:

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Initialize variables to keep track of the maximum amount of money robbed at the previous and current houses
        prev, curr = 0, 0

        # Iterate through the houses
        for n in nums:
            # Calculate the maximum amount of money that can be robbed at the current house
            # It is the maximum of either robbing the current house and the money robbed at the house before the previous one (prev),
            # or skipping the current house and taking the maximum amount from the previous house (curr)
            temp = max(n + prev, curr)

            # Update the variables for the next iteration
            prev, curr = curr, temp

        # The final result is the maximum amount of money that can be robbed at the last house
        return curr

Explanation:#

The provided code is a Python implementation of the “House Robber” problem using a dynamic programming approach. It’s part of a class Solution and includes a method rob that takes a list of integers nums as input and returns the maximum amount of money that can be robbed without alerting the police.

The key idea of the algorithm is to maintain two variables, prev and curr, which represent the maximum amount of money that can be robbed up to the previous house and the current house, respectively. The algorithm iterates through the houses, updating these variables based on the maximum amount that can be robbed at the current house, considering the constraint of not robbing adjacent houses.

The loop calculates a temporary variable temp that represents the maximum amount of money that can be robbed at the current house. It considers two scenarios: either robbing the current house and adding the money robbed at the house before the previous one (n + prev), or skipping the current house and taking the maximum amount from the previous house (curr). The maximum of these two scenarios is assigned to temp.

The prev and curr variables are then updated for the next iteration. prev is set to the previous value of curr, and curr is set to the calculated temp.

The final result is the value stored in the curr variable, representing the maximum amount of money that can be robbed at the last house. This value is returned as the result of the rob method.

The provided test cases at the end demonstrate the usage of the rob method with different input arrays.

Test cases:#

Here’s how you can use this solution:

# Example 1:
sol = Solution()

nums1 = [1, 2, 3, 1]
print(sol.rob(nums1))  # Output: 4

4

# Example 2:
nums2 = [2, 7, 9, 3, 1]
print(sol.rob(nums2))  # Output: 12

12

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code.

Time Complexity:#

The time complexity of the code is O(n), where n is the number of houses. The algorithm iterates through the array once, and in each iteration, it performs constant time operations. The loop runs for each house, and the number of operations inside the loop is independent of the input size. Therefore, the overall time complexity is linear, O(n).

Space Complexity:#

The space complexity is O(1), constant space. The algorithm uses only a constant amount of extra space regardless of the input size. The variables prev, curr, and temp are the only additional variables used, and they do not depend on the size of the input array. Thus, the space complexity is constant, O(1).

In summary:

  • Time Complexity: O(n)

  • Space Complexity: O(1)

Challenging Exercises:#

  1. Variation with Maximum Number of Houses to Rob: Modify the problem to include an additional constraint: you are allowed to rob at most ‘k’ houses without triggering the alarm. Find the maximum amount you can rob under this new constraint.

  2. Robbing in a Circular Street: Extend the problem to a circular street where the first and last houses are adjacent. You cannot rob both the first and last houses simultaneously. Find the maximum amount you can rob in this circular setting.

Link to Problem: To see the House Robber problem on LeetCode, click here!