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.
For example:
nums = [1,2,3,1]
The output should be 4.
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.nums = [2,7,9,3,1]
The output should be 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.Write a function to solve this problem efficiently.
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:
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:
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
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:
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]
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. |