We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

House Robber II

Number: 213

Difficulty: Medium

Paid? No

Companies: Databricks, Google, Microsoft, Meta, Amazon, Docusign, Apple, TikTok, Nordstrom, Uber, PhonePe, Adobe, Bloomberg, Yahoo, LinkedIn, ByteDance, thoughtspot

Problem Description

A robber wants to steal from houses arranged in a circle. Each house has a certain amount of money, but robbing two adjacent houses will trigger the security system. Given an array of non-negative integers representing the money in each house, determine the maximum amount of money that can be robbed without alerting the police.

Key Insights

  • The houses are arranged in a circle, meaning the first and last houses are neighbors.
  • Because of the circular arrangement, you cannot rob both the first and last houses.
  • The problem can be reduced into two separate linear House Robber problems:
    • One considering houses from index 1 to n-1 (exclude the first house).
    • The other considering houses from index 0 to n-2 (exclude the last house).
  • Use dynamic programming with constant space (using two variables) to compute the solution for a linear array of houses.

Space and Time Complexity

Time Complexity: O(n), where n is the number of houses. Space Complexity: O(1), as only a constant amount of extra space is used.

Solution

To handle the circular dependency, we solve two linear versions of the problem:

  1. Exclude the first house and calculate the maximum rob amount for houses from index 1 to n-1.
  2. Exclude the last house and calculate the maximum rob amount for houses from index 0 to n-2. Then, the final answer is the maximum of these two calculated values. We use dynamic programming by iterating through the list and at each step, calculating the maximum money that can be robbed up to that point with two variables.

Code Solutions

# Python solution for House Robber II

def rob(nums):
    # Helper function to handle the linear House Robber problem.
    def rob_linear(houses):
        prev_max, curr_max = 0, 0
        for money in houses:
            temp = curr_max
            curr_max = max(curr_max, prev_max + money)
            prev_max = temp
        return curr_max

    n = len(nums)
    # When there's only one house, just return its value.
    if n == 1:
        return nums[0]
    
    # Rob excluding the first house and excluding the last house.
    return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

# Test example
print(rob([2, 3, 2]))  # Expected output: 3
← Back to All Questions