Jobs

Interviews

Discussions

House Robber II

Medium

House Robber II

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `nums` contain negative numbers, zero, or only positive integers?
If the input array `nums` is empty or null, what should I return?
Does 'adjacent houses' refer to houses that are immediately next to each other in the array, or can there be skipped houses in between?
Since the houses are in a circle, does robbing the first house prevent me from robbing the *last* house, and vice-versa, or are there other edge cases to consider regarding the circular arrangement?
If the array only contains one house, should I rob it or not?

Brute Force Solution

Approach

We're trying to find the most money we can steal from houses in a circle, but we can't rob adjacent houses. The brute force way is to consider every possible combination of houses to rob and see which one gives us the most money without robbing neighbors.

Here's how the algorithm would work step-by-step:

First, realize since the houses are in a circle, robbing the first house means we can't rob the last, and vice-versa.
So, we can think of this as two separate problems: one where we rob the first house, and one where we don't.
For each of these situations, let's start by considering robbing no houses at all. Calculate the total money stolen, which would be zero.
Then, consider robbing only the first house (or second, or third, etc.). Check if robbing this house is allowed based on the 'no adjacent houses' rule. If yes, record the total money stolen so far.
Next, consider robbing two houses. Check all possible pairs of houses. If the two houses are not next to each other, add up their money. Record the total stolen money, but ONLY if the houses are not next to each other.
Continue this process for robbing three houses, four houses, and so on, up to robbing almost all of the houses. Each time making sure not to rob adjacent houses.
For each combination of houses, keep track of the total money we would steal.
After going through every single possibility, compare the total money stolen from all of the possibilities we recorded.
The highest amount of money we could have stolen without robbing adjacent houses is our answer.

Code Implementation

def house_robber_two_brute_force(houses):
    number_of_houses = len(houses)

    if number_of_houses == 0:
        return 0

    maximum_money_stolen = 0

    # Consider two cases: rob the first house or don't
    for rob_first_house in [True, False]:
        for number_of_houses_to_rob in range(number_of_houses + 1):
            for combination_mask in range(2**number_of_houses):
                robbed_houses = []
                money_stolen = 0
                houses_robbed_count = 0

                # Check if this combination is valid
                for house_index in range(number_of_houses):
                    if (combination_mask >> house_index) & 1:
                        robbed_houses.append(house_index)
                        houses_robbed_count += 1

                if houses_robbed_count != number_of_houses_to_rob:
                    continue

                # Check for adjacency and first/last house rule.
                valid_combination = True
                if rob_first_house:
                    if 0 not in robbed_houses:
                        continue

                    if number_of_houses - 1 in robbed_houses:
                        continue
                
                for i in range(len(robbed_houses)):
                    if i > 0:
                        if robbed_houses[i] - robbed_houses[i - 1] == 1:
                            valid_combination = False
                            break
                
                if valid_combination:
                    for house_index in robbed_houses:
                        money_stolen += houses[house_index]

                    maximum_money_stolen = max(maximum_money_stolen, money_stolen)

    return maximum_money_stolen

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible combinations of houses. For each house, we either choose to rob it or not, leading to 2 options per house. With n houses, this generates 2^n possible combinations to evaluate. The operation of 'checking if houses are adjacent' is O(n) in the worst case to loop through all the robbed houses. Thus, total operations are 2^n * O(n) which simplifies to O(2^n) since the exponential term dominates. The brute-force method examines a power set of the input.

Space Complexity

O(2^N) – The described brute force approach explores every possible combination of houses. The algorithm essentially generates all subsets of houses to consider for robbing. In the worst-case, it needs to 'keep track of the total money we would steal' for each combination and potentially store these combinations implicitly or explicitly while exploring all possibilities. Since there are 2^N possible subsets for N houses, the space complexity is exponential, O(2^N).

Optimal Solution

Approach

This problem is tricky because the first and last houses are connected, creating a circular arrangement. The clever approach is to break this circle into two separate lines of houses, solving each independently, and then choosing the better outcome.

Here's how the algorithm would work step-by-step:

Recognize that you can't rob both the first and last house because they're neighbors in a circle.
Consider two possibilities: First, calculate the most money you can get by robbing houses starting from the beginning but excluding the very last house.
Second, calculate the most money you can get by robbing houses starting from the second house and going to the end, skipping the very first house.
For each of these possibilities, use a strategy where you either rob the current house AND add the money from two houses before, OR skip the current house and take the maximum amount of money you could get until the previous house. Make this decision for each house.
Compare the total money you could get from the first possibility versus the second possibility, and pick the higher amount.

Code Implementation

def house_robber_two(house_values):
    number_of_houses = len(house_values)
    if number_of_houses == 0:
        return 0
    if number_of_houses == 1:
        return house_values[0]

    def rob_linear_houses(house_values_subset):
        number_of_houses_subset = len(house_values_subset)
        if number_of_houses_subset == 0:
            return 0

        maximum_money_at_house = [0] * number_of_houses_subset
        maximum_money_at_house[0] = house_values_subset[0]

        if number_of_houses_subset > 1:
            maximum_money_at_house[1] = max(house_values_subset[0], house_values_subset[1])

        for i in range(2, number_of_houses_subset):
            # Decide whether to rob current or skip
            maximum_money_at_house[i] = max(house_values_subset[i] + maximum_money_at_house[i - 2], maximum_money_at_house[i - 1])

        return maximum_money_at_house[number_of_houses_subset - 1]

    # Exclude the last house
    max_money_excluding_last_house = rob_linear_houses(house_values[:-1])

    # Exclude the first house
    max_money_excluding_first_house = rob_linear_houses(house_values[1:])

    # Return the maximum of the two scenarios
    return max(max_money_excluding_first_house, max_money_excluding_last_house)

Big(O) Analysis

Time Complexity

O(n) – The solution involves calculating the maximum robbed amount for two subproblems, each representing a linear sequence of houses. For each of these subproblems, we iterate through a portion of the input array of size n, making constant-time decisions (rob current house vs. skip it) for each house. Thus, we perform a single pass through the array (or portions of it), leading to a linear relationship between the input size and the number of operations. Consequently, the time complexity is O(n).

Space Complexity

O(1) – The algorithm calculates the maximum robbery amount in two scenarios by iterating through the houses but does not store intermediate results in data structures that scale with the input size. It only uses a constant number of variables to keep track of the current maximum robbery amounts for each house. Therefore, the auxiliary space required is constant regardless of the number of houses, N, making the space complexity O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the input array is empty since there are no houses to rob.
Array with one house	Return the value of the single house since we can only rob it.
Array with two houses	Return the maximum value of the two houses since we can only rob one.
All houses have a value of 0	Return 0 since robbing any house yields 0 profit.
Houses with negative values (invalid scenario)	Raise an exception or return an error code since house values cannot be negative in the given problem context; alternatively, if permissible, treat negative values as valid amounts and the algorithm should find optimal negative gain.
Very large house values that can cause integer overflow during summation	Use a data type with a larger range like long to prevent integer overflow when calculating the maximum robbed amount, if language supports it.
Large input array to ensure algorithm scales efficiently	The dynamic programming solution avoids unnecessary calculations and has a linear time complexity (O(n)), making it efficient for large input arrays.
Circular dependency between first and last house	The solution handles the circular dependency by considering two separate scenarios: robbing the first house (and not the last) and robbing the last house (and not the first), then taking the maximum of the two scenarios.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `nums` contain negative numbers, zero, or only positive integers?
If the input array `nums` is empty or null, what should I return?
Does 'adjacent houses' refer to houses that are immediately next to each other in the array, or can there be skipped houses in between?
Since the houses are in a circle, does robbing the first house prevent me from robbing the *last* house, and vice-versa, or are there other edge cases to consider regarding the circular arrangement?
If the array only contains one house, should I rob it or not?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, realize since the houses are in a circle, robbing the first house means we can't rob the last, and vice-versa.
So, we can think of this as two separate problems: one where we rob the first house, and one where we don't.
For each of these situations, let's start by considering robbing no houses at all. Calculate the total money stolen, which would be zero.
Then, consider robbing only the first house (or second, or third, etc.). Check if robbing this house is allowed based on the 'no adjacent houses' rule. If yes, record the total money stolen so far.
Next, consider robbing two houses. Check all possible pairs of houses. If the two houses are not next to each other, add up their money. Record the total stolen money, but ONLY if the houses are not next to each other.
Continue this process for robbing three houses, four houses, and so on, up to robbing almost all of the houses. Each time making sure not to rob adjacent houses.
For each combination of houses, keep track of the total money we would steal.
After going through every single possibility, compare the total money stolen from all of the possibilities we recorded.
The highest amount of money we could have stolen without robbing adjacent houses is our answer.

Code Implementation

def house_robber_two_brute_force(houses):
    number_of_houses = len(houses)

    if number_of_houses == 0:
        return 0

    maximum_money_stolen = 0

    # Consider two cases: rob the first house or don't
    for rob_first_house in [True, False]:
        for number_of_houses_to_rob in range(number_of_houses + 1):
            for combination_mask in range(2**number_of_houses):
                robbed_houses = []
                money_stolen = 0
                houses_robbed_count = 0

                # Check if this combination is valid
                for house_index in range(number_of_houses):
                    if (combination_mask >> house_index) & 1:
                        robbed_houses.append(house_index)
                        houses_robbed_count += 1

                if houses_robbed_count != number_of_houses_to_rob:
                    continue

                # Check for adjacency and first/last house rule.
                valid_combination = True
                if rob_first_house:
                    if 0 not in robbed_houses:
                        continue

                    if number_of_houses - 1 in robbed_houses:
                        continue
                
                for i in range(len(robbed_houses)):
                    if i > 0:
                        if robbed_houses[i] - robbed_houses[i - 1] == 1:
                            valid_combination = False
                            break
                
                if valid_combination:
                    for house_index in robbed_houses:
                        money_stolen += houses[house_index]

                    maximum_money_stolen = max(maximum_money_stolen, money_stolen)

    return maximum_money_stolen

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that you can't rob both the first and last house because they're neighbors in a circle.
Consider two possibilities: First, calculate the most money you can get by robbing houses starting from the beginning but excluding the very last house.
Second, calculate the most money you can get by robbing houses starting from the second house and going to the end, skipping the very first house.
For each of these possibilities, use a strategy where you either rob the current house AND add the money from two houses before, OR skip the current house and take the maximum amount of money you could get until the previous house. Make this decision for each house.
Compare the total money you could get from the first possibility versus the second possibility, and pick the higher amount.

Code Implementation

def house_robber_two(house_values):
    number_of_houses = len(house_values)
    if number_of_houses == 0:
        return 0
    if number_of_houses == 1:
        return house_values[0]

    def rob_linear_houses(house_values_subset):
        number_of_houses_subset = len(house_values_subset)
        if number_of_houses_subset == 0:
            return 0

        maximum_money_at_house = [0] * number_of_houses_subset
        maximum_money_at_house[0] = house_values_subset[0]

        if number_of_houses_subset > 1:
            maximum_money_at_house[1] = max(house_values_subset[0], house_values_subset[1])

        for i in range(2, number_of_houses_subset):
            # Decide whether to rob current or skip
            maximum_money_at_house[i] = max(house_values_subset[i] + maximum_money_at_house[i - 2], maximum_money_at_house[i - 1])

        return maximum_money_at_house[number_of_houses_subset - 1]

    # Exclude the last house
    max_money_excluding_last_house = rob_linear_houses(house_values[:-1])

    # Exclude the first house
    max_money_excluding_first_house = rob_linear_houses(house_values[1:])

    # Return the maximum of the two scenarios
    return max(max_money_excluding_first_house, max_money_excluding_last_house)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the input array is empty since there are no houses to rob.
Array with one house	Return the value of the single house since we can only rob it.
Array with two houses	Return the maximum value of the two houses since we can only rob one.
All houses have a value of 0	Return 0 since robbing any house yields 0 profit.
Houses with negative values (invalid scenario)	Raise an exception or return an error code since house values cannot be negative in the given problem context; alternatively, if permissible, treat negative values as valid amounts and the algorithm should find optimal negative gain.
Very large house values that can cause integer overflow during summation	Use a data type with a larger range like long to prevent integer overflow when calculating the maximum robbed amount, if language supports it.
Large input array to ensure algorithm scales efficiently	The dynamic programming solution avoids unnecessary calculations and has a linear time complexity (O(n)), making it efficient for large input arrays.
Circular dependency between first and last house	The solution handles the circular dependency by considering two separate scenarios: robbing the first house (and not the last) and robbing the last house (and not the first), then taking the maximum of the two scenarios.