algoadvance

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and you need to determine the maximum amount of money you can rob tonight without alerting the police. The constraint is that adjacent houses have security systems connected, so you cannot rob two directly adjacent houses.

Example:

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

Constraints:

Clarifying Questions

  1. Q: Can the input list be empty? A: Yes, if the input list is empty, the maximum amount of money that can be robbed is 0.

  2. Q: Can the input list contain non-integer values or negative integers? A: No, the problem specifies that the values will be non-negative integers within the range [0, 400].

Strategy

The problem can be solved using dynamic programming (DP). We can define a DP table where dp[i] represents the maximum amount of money that can be robbed from the first i houses.

  1. If the input list is empty, return 0.
  2. If there is only one house, rob that house.
  3. For each house, decide whether to rob it or not:
    • If we rob the current house, we should add its value to the maximum value found two houses before.
    • If we do not rob the current house, keep the maximum value found up to the previous house.
  4. Fill in the DP table using the formula:
    • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  5. The result will be the maximum value found in the DP table.

Code

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    n = len(nums)
    dp = [0] * n
    
    # Initialize the base cases
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]

Time Complexity

The time complexity of the above solution is O(n), where n is the length of the input list nums, because we are iterating through the list once while computing values for the DP table.

The space complexity is also O(n) due to the DP table storing values for each house. However, we can optimize the space complexity to O(1) since we only need the last two computed values at each step.

Optimized Code for Space Complexity

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev1, prev2 = nums[0], max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        current = max(prev2, prev1 + nums[i])
        prev1 = prev2
        prev2 = current
    
    return prev2

In the optimized version, we maintain only the last two maximum values, resulting in space complexity of O(1) and the same time complexity of O(n).

Try our interview co-pilot at AlgoAdvance.com