Jobs

Interviews

Discussions

House Robber

Medium

Apple

4 views

Topics:

ArraysDynamic Programming

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint is that adjacent houses have security systems connected. If two adjacent houses are broken into on the same night, the police will be automatically contacted.

Given an integer array nums representing the amount of money in each house, return 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).
Total amount you can rob = 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).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

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

House Robber

Medium

Apple

4 views

Topics:

ArraysDynamic Programming

Given an integer array nums representing the amount of money in each house, return 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).
Total amount you can rob = 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).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

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

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:

What is the range of values for the money in each house (nums[i])? Can the values be negative, zero, or only positive?
What is the expected behavior if the input array is null or empty? Should I return 0, throw an exception, or handle it in another way?
What is the maximum size (length) of the `nums` array?
Can you provide a concrete example to illustrate the expected output for a specific input, especially regarding edge cases?
Is there any constraint on the type of returned value, for example, can I return a float or must it be an integer?

Brute Force Solution

Approach

The brute force approach to the House Robber problem involves considering every single combination of houses you could rob. We look at each combination and calculate the total money we would get if we robbed those houses. Finally, we determine the maximum amount of money we could rob from any of the combinations we considered.

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

Start by considering robbing no houses at all, resulting in zero money.
Then, consider robbing only the first house, then only the second house, then only the third house, and so on, up to robbing only the last house.
Next, consider robbing every possible pair of houses: the first and second, the first and third, the first and fourth, and so on. Remember that you can't rob adjacent houses.
Continue this process by considering robbing every possible group of three houses, then four houses, then five houses, making sure that no two houses in any group are adjacent.
For each combination of houses, calculate the total money you would obtain by robbing those houses.
After considering all possible combinations of houses, compare the total money from each combination.
Select the combination of houses that gives you the maximum amount of money. This is the solution.

Code Implementation

def house_robber_brute_force(house_values):
    number_of_houses = len(house_values)
    maximum_money_robbed = 0

    # Iterate through all possible combinations of houses
    for i in range(1 << number_of_houses):
        current_money_robbed = 0
        robbed_houses = []

        # Determine which houses are robbed in the current combination
        for j in range(number_of_houses):
            if (i >> j) & 1:
                robbed_houses.append(j)

        # Validate that no adjacent houses are robbed
        is_valid_combination = True

        # Ensures that we only consider valid sets of houses.
        for k in range(len(robbed_houses) - 1):
            if robbed_houses[k + 1] - robbed_houses[k] == 1:
                is_valid_combination = False
                break

        if is_valid_combination:
            # Calculate the total money robbed for this valid combination
            for house_index in robbed_houses:
                current_money_robbed += house_values[house_index]

            # Update maximum money robbed if the current combination is better
            maximum_money_robbed = max(maximum_money_robbed, current_money_robbed)

    return maximum_money_robbed

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible subsets of houses. For each house, we either rob it or we don't. This results in 2 options for each of the n houses. Therefore, we examine 2 * 2 * ... * 2 (n times) = 2^n possible combinations of houses to rob. Thus, the time complexity grows exponentially with the number of houses.

Space Complexity

O(1) – The brute force approach, as described, does not utilize any auxiliary data structures. It iterates through combinations and calculates the maximum, but it doesn't store these combinations or intermediate results in a way that scales with the input size, N (the number of houses). The algorithm only requires a constant amount of extra memory to keep track of the current maximum amount and indices, independent of N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The core idea is to avoid recomputing the best outcome for each house. Instead, we'll make a decision for each house: either rob it or don't rob it, and keep track of the best amount we can steal up to that point based on these choices. By the time we reach the last house, we'll know the best overall amount we could have stolen.

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

Think about robbing the houses one by one, going from left to right.
For each house, we have two choices: rob it or skip it.
If we rob the current house, we cannot rob the previous house. But we add the current house's value to the best amount we could have stolen up to two houses ago.
If we skip the current house, then our best amount stolen is the same as the best amount we could have stolen from the previous house.
At each house, we choose the option that gives us the higher amount of money: robbing it or skipping it.
Keep track of the best amount stolen so far at each house.
The best amount stolen at the last house is the answer.

Code Implementation

def house_robber(house_values):
    number_of_houses = len(house_values)

    if number_of_houses == 0:
        return 0

    # Store the maximum amount robbed up to each house.
    max_money_at_house = [0] * number_of_houses

    max_money_at_house[0] = house_values[0]

    if number_of_houses > 1:
        # The max money at the second house is either robbing it or the first.
        max_money_at_house[1] = max(house_values[0], house_values[1])

    for i in range(2, number_of_houses):
        # Determine the max money robbed up to the current house.
        max_money_at_house[i] = max(
            house_values[i] + max_money_at_house[i - 2],
            max_money_at_house[i - 1],
        )

    # The final element is the maximum money that can be robbed.
    return max_money_at_house[number_of_houses - 1]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of houses exactly once. For each house, it performs a constant amount of work: comparing two values (robbing vs. skipping) and updating the maximum amount robbed so far. Since the number of operations grows linearly with the number of houses (n), the time complexity is O(n).

Space Complexity

O(1) – The provided description outlines an iterative approach where we only keep track of the best amount stolen so far at each house. This suggests we only need a fixed number of variables to store intermediate maximum values. The space used does not scale with the number of houses (N) because we are updating existing variables rather than allocating new space dependent on the input size. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 because there are no houses to rob, yielding no profit.
Single element array	Return the value of the single element since you can rob that one house.
Two element array	Return the maximum of the two elements because you can only rob one.
Array with all zeros	Return 0 because robbing any house yields nothing.
Array with all identical positive values	If the array has an even length, return (array length/2) * value; if odd, return ((array length + 1)/2) * value.
Array with a large range of values (potential for integer overflow)	Use a data type that can accommodate large sums, such as long, to prevent overflow.
Large input array (performance consideration)	The dynamic programming solution with O(n) time complexity should scale efficiently for large inputs, as it avoids unnecessary recalculations.
Array with a combination of large and small numbers (potential performance issues with naive recursive solution)	Dynamic programming provides an optimal solution by avoiding repeated calls for smaller subproblems.

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:

What is the range of values for the money in each house (nums[i])? Can the values be negative, zero, or only positive?
What is the expected behavior if the input array is null or empty? Should I return 0, throw an exception, or handle it in another way?
What is the maximum size (length) of the `nums` array?
Can you provide a concrete example to illustrate the expected output for a specific input, especially regarding edge cases?
Is there any constraint on the type of returned value, for example, can I return a float or must it be an integer?

Brute Force Solution

Approach

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

Start by considering robbing no houses at all, resulting in zero money.
Then, consider robbing only the first house, then only the second house, then only the third house, and so on, up to robbing only the last house.
Next, consider robbing every possible pair of houses: the first and second, the first and third, the first and fourth, and so on. Remember that you can't rob adjacent houses.
Continue this process by considering robbing every possible group of three houses, then four houses, then five houses, making sure that no two houses in any group are adjacent.
For each combination of houses, calculate the total money you would obtain by robbing those houses.
After considering all possible combinations of houses, compare the total money from each combination.
Select the combination of houses that gives you the maximum amount of money. This is the solution.

Code Implementation

def house_robber_brute_force(house_values):
    number_of_houses = len(house_values)
    maximum_money_robbed = 0

    # Iterate through all possible combinations of houses
    for i in range(1 << number_of_houses):
        current_money_robbed = 0
        robbed_houses = []

        # Determine which houses are robbed in the current combination
        for j in range(number_of_houses):
            if (i >> j) & 1:
                robbed_houses.append(j)

        # Validate that no adjacent houses are robbed
        is_valid_combination = True

        # Ensures that we only consider valid sets of houses.
        for k in range(len(robbed_houses) - 1):
            if robbed_houses[k + 1] - robbed_houses[k] == 1:
                is_valid_combination = False
                break

        if is_valid_combination:
            # Calculate the total money robbed for this valid combination
            for house_index in robbed_houses:
                current_money_robbed += house_values[house_index]

            # Update maximum money robbed if the current combination is better
            maximum_money_robbed = max(maximum_money_robbed, current_money_robbed)

    return maximum_money_robbed

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think about robbing the houses one by one, going from left to right.
For each house, we have two choices: rob it or skip it.
If we rob the current house, we cannot rob the previous house. But we add the current house's value to the best amount we could have stolen up to two houses ago.
If we skip the current house, then our best amount stolen is the same as the best amount we could have stolen from the previous house.
At each house, we choose the option that gives us the higher amount of money: robbing it or skipping it.
Keep track of the best amount stolen so far at each house.
The best amount stolen at the last house is the answer.

Code Implementation

def house_robber(house_values):
    number_of_houses = len(house_values)

    if number_of_houses == 0:
        return 0

    # Store the maximum amount robbed up to each house.
    max_money_at_house = [0] * number_of_houses

    max_money_at_house[0] = house_values[0]

    if number_of_houses > 1:
        # The max money at the second house is either robbing it or the first.
        max_money_at_house[1] = max(house_values[0], house_values[1])

    for i in range(2, number_of_houses):
        # Determine the max money robbed up to the current house.
        max_money_at_house[i] = max(
            house_values[i] + max_money_at_house[i - 2],
            max_money_at_house[i - 1],
        )

    # The final element is the maximum money that can be robbed.
    return max_money_at_house[number_of_houses - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 because there are no houses to rob, yielding no profit.
Single element array	Return the value of the single element since you can rob that one house.
Two element array	Return the maximum of the two elements because you can only rob one.
Array with all zeros	Return 0 because robbing any house yields nothing.
Array with all identical positive values	If the array has an even length, return (array length/2) * value; if odd, return ((array length + 1)/2) * value.
Array with a large range of values (potential for integer overflow)	Use a data type that can accommodate large sums, such as long, to prevent overflow.
Large input array (performance consideration)	The dynamic programming solution with O(n) time complexity should scale efficiently for large inputs, as it avoids unnecessary recalculations.
Array with a combination of large and small numbers (potential performance issues with naive recursive solution)	Dynamic programming provides an optimal solution by avoiding repeated calls for smaller subproblems.