Jobs

Interviews

Discussions

House Robber

Medium

Walmart

0 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 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.

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

Walmart

0 views

Topics:

ArraysDynamic Programming

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.

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 integers in the `nums` array, and can they be negative?
What should I return if the input array `nums` is null or empty?
Are the integers in the array guaranteed to be integers, or could they be floating-point numbers?
Is the input array `nums` read-only, or am I allowed to modify it?
Could you provide a few more example inputs and their expected outputs, especially for edge cases like a single house or two houses?

Brute Force Solution

Approach

The brute force approach for the House Robber problem is like trying every possible combination of houses you could rob. It explores each selection of houses, calculates the total loot for that selection, and then determines the best possible loot.

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

Consider the option where you rob only the first house.
Consider the option where you rob only the second house.
Consider the option where you rob the first and third houses, skipping the second.
Consider the option where you rob the second and fourth houses, skipping the third.
Keep creating every possible combination of houses you could rob, remembering you can't rob adjacent houses.
For each combination, add up the money you'd get from robbing those houses.
Once you've explored every possible combination, compare the total money you'd get from each one.
The combination that gives you the most money is the answer.

Code Implementation

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

    def rob(current_index):
        # Base case: if we've reached the end, return 0
        if current_index >= number_of_houses:
            return 0

        # Option 1: Rob the current house and skip the next
        rob_current_house = house_values[current_index] + rob(current_index + 2)

        # Option 2: Skip the current house and move to the next
        skip_current_house = rob(current_index + 1)

        # Choose the option that yields the maximum loot
        return max(rob_current_house, skip_current_house)

    return rob(0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible subsets of houses, where each house can either be robbed or not robbed. For n houses, there are 2^n possible combinations (subsets) to consider. Therefore, the time complexity is O(2^n) because, in the worst case, we examine every single one of these subsets to find the combination that yields the maximum loot without robbing adjacent houses. The number of operations grows exponentially with the number of houses.

Space Complexity

O(2^N) – The brute force approach explores every possible combination of houses. In the worst-case scenario, each house could either be robbed or not robbed, leading to 2^N possible combinations where N is the number of houses. Although the explanation doesn't explicitly mention storing all combinations simultaneously, evaluating each combination requires creating intermediate sums and storing the best loot found so far. Therefore, the maximum depth of the implicit decision tree representing these combinations is N, but the number of branches explored grows exponentially, leading to a space complexity proportional to 2^N in the worst case due to the implicit call stack or data structures used to keep track of the different combinations being explored. This results in a space complexity of O(2^N).

Optimal Solution

Approach

The best way to solve this problem is to think about it one house at a time and make a smart choice: rob it, or don't. We can figure out the most money we can get up to that house based on our earlier choices, without having to check every possible combination.

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

Start with the first house. The most money you can have is just the value of that house.
Move to the second house. Now, you have two options: rob the second house, or don't. If you rob it, you can't rob the first. So, compare the value of the second house with the value of the first house, and pick the higher one. This is the most money you can have up to the second house.
Now, for each house after the second, you again have two options: rob it, or don't. If you rob the current house, you can't rob the previous one. So, add the value of the current house to the most money you could have up to *two* houses ago. Compare this with the most money you could have if you *don't* rob the current house (which is just the most money you could have up to the *previous* house).
Pick the bigger of these two amounts. This is the most money you can have up to the current house.
Keep doing this for all the houses. The most money you can have at the very 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 max loot obtainable up to each house
    max_loot_at_house = [0] * number_of_houses

    max_loot_at_house[0] = house_values[0]

    if number_of_houses > 1:
        # Determine max loot up to the second house
        max_loot_at_house[1] = max(house_values[0],
                                   house_values[1])

    # Build up solutions using prior results
    for current_house in range(2, number_of_houses):
        # Decide: rob this house, or skip it.
        max_loot_robbing_current_house = house_values[current_house] +\
            max_loot_at_house[current_house - 2]

        # Consider not robbing the current house
        max_loot_skipping_current_house = max_loot_at_house[current_house - 1]

        # Storing the best choice at each stage
        max_loot_at_house[current_house] = max(
            max_loot_robbing_current_house,
            max_loot_skipping_current_house
        )

    return max_loot_at_house[number_of_houses - 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of houses, `nums`, once. For each house, it performs a constant amount of work: comparing two values and updating a maximum value. Therefore, the time complexity is directly proportional to the number of houses, n, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm keeps track of the maximum amount of money that can be robbed up to the current house by using a constant number of variables to store intermediate results (e.g., maximum robbed amount at the previous house, maximum robbed amount at two houses ago). The space required for these variables does not depend on the number of houses (N). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as there's nothing to rob.
Array with a single house	Return the value of the single house since there are no adjacent houses.
Array with two houses	Return the maximum of the two houses' values.
Array with all houses having zero value	Return 0, as there's no profit to be made.
Array with all houses having the same non-zero value	The robber will pick every other house, so calculate based on array length being even or odd.
Large input array causing potential integer overflow in intermediate calculations	Use long data type to store the maximum robbed amount.
Array containing extreme boundary values (e.g., Integer.MAX_VALUE)	Ensure that intermediate calculations and the final result don't overflow by using long data type and carefully considering addition operations.
Array with a mix of large and small values that causes Integer overflow when added	Use long data types for dp array to avoid overflow.

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 integers in the `nums` array, and can they be negative?
What should I return if the input array `nums` is null or empty?
Are the integers in the array guaranteed to be integers, or could they be floating-point numbers?
Is the input array `nums` read-only, or am I allowed to modify it?
Could you provide a few more example inputs and their expected outputs, especially for edge cases like a single house or two houses?

Brute Force Solution

Approach

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

Consider the option where you rob only the first house.
Consider the option where you rob only the second house.
Consider the option where you rob the first and third houses, skipping the second.
Consider the option where you rob the second and fourth houses, skipping the third.
Keep creating every possible combination of houses you could rob, remembering you can't rob adjacent houses.
For each combination, add up the money you'd get from robbing those houses.
Once you've explored every possible combination, compare the total money you'd get from each one.
The combination that gives you the most money is the answer.

Code Implementation

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

    def rob(current_index):
        # Base case: if we've reached the end, return 0
        if current_index >= number_of_houses:
            return 0

        # Option 1: Rob the current house and skip the next
        rob_current_house = house_values[current_index] + rob(current_index + 2)

        # Option 2: Skip the current house and move to the next
        skip_current_house = rob(current_index + 1)

        # Choose the option that yields the maximum loot
        return max(rob_current_house, skip_current_house)

    return rob(0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with the first house. The most money you can have is just the value of that house.
Move to the second house. Now, you have two options: rob the second house, or don't. If you rob it, you can't rob the first. So, compare the value of the second house with the value of the first house, and pick the higher one. This is the most money you can have up to the second house.
Now, for each house after the second, you again have two options: rob it, or don't. If you rob the current house, you can't rob the previous one. So, add the value of the current house to the most money you could have up to *two* houses ago. Compare this with the most money you could have if you *don't* rob the current house (which is just the most money you could have up to the *previous* house).
Pick the bigger of these two amounts. This is the most money you can have up to the current house.
Keep doing this for all the houses. The most money you can have at the very 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 max loot obtainable up to each house
    max_loot_at_house = [0] * number_of_houses

    max_loot_at_house[0] = house_values[0]

    if number_of_houses > 1:
        # Determine max loot up to the second house
        max_loot_at_house[1] = max(house_values[0],
                                   house_values[1])

    # Build up solutions using prior results
    for current_house in range(2, number_of_houses):
        # Decide: rob this house, or skip it.
        max_loot_robbing_current_house = house_values[current_house] +\
            max_loot_at_house[current_house - 2]

        # Consider not robbing the current house
        max_loot_skipping_current_house = max_loot_at_house[current_house - 1]

        # Storing the best choice at each stage
        max_loot_at_house[current_house] = max(
            max_loot_robbing_current_house,
            max_loot_skipping_current_house
        )

    return max_loot_at_house[number_of_houses - 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as there's nothing to rob.
Array with a single house	Return the value of the single house since there are no adjacent houses.
Array with two houses	Return the maximum of the two houses' values.
Array with all houses having zero value	Return 0, as there's no profit to be made.
Array with all houses having the same non-zero value	The robber will pick every other house, so calculate based on array length being even or odd.
Large input array causing potential integer overflow in intermediate calculations	Use long data type to store the maximum robbed amount.
Array containing extreme boundary values (e.g., Integer.MAX_VALUE)	Ensure that intermediate calculations and the final result don't overflow by using long data type and carefully considering addition operations.
Array with a mix of large and small values that causes Integer overflow when added	Use long data types for dp array to avoid overflow.