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]
In this case, the optimal solution is to rob house 1 (money = 1) and then rob house 3 (money = 3). The total amount you can rob is 1 + 3 = 4.
As another example:
nums = [2,7,9,3,1]
In this case, you could rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). The total amount you can rob is 2 + 9 + 1 = 12. There is no way to rob more money without robbing adjacent houses.
Describe an algorithm to solve this problem efficiently. What is the time complexity of your solution? What is the space complexity?
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.
A brute force approach would involve trying all possible combinations of robbing houses and finding the combination that yields the maximum amount without robbing adjacent houses. This can be done using recursion.
This approach leads to overlapping subproblems and is highly inefficient.
def rob_recursive(nums):
def rob(i):
if i >= len(nums):
return 0
# Rob current house + skip the next
rob_current = nums[i] + rob(i + 2)
# Don't rob current house
skip_current = rob(i + 1)
return max(rob_current, skip_current)
return rob(0)
O(2n), where n is the number of houses.
O(n) due to the recursion depth.
The optimal approach uses dynamic programming to avoid recomputation of overlapping subproblems.
dp
where dp[i]
represents the maximum amount that can be robbed up to house i
.dp[0] = nums[0]
(If there is only one house, rob it).dp[1] = max(nums[0], nums[1])
(If there are two houses, rob the one with maximum amount).i > 1
, dp[i] = max(dp[i-1], dp[i-2] + nums[i])
.
dp[i-1]
means we don't rob house i
.dp[i-2] + nums[i]
means we rob house i
and the maximum amount up to i-2
.dp[n-1]
, where n
is the number of houses.def rob(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[n - 1]
Alternatively, we can optimize space complexity to O(1) by storing only the last two values.
def rob_optimized(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
prev1 = nums[0]
prev2 = max(nums[0], nums[1]) if n > 1 else nums[0]
for i in range(2, n):
current = max(prev2, prev1 + nums[i])
prev1 = prev2
prev2 = current
return prev2
O(n), where n is the number of houses.
O(n) for the DP array in the first DP solution. O(1) for the space-optimized version.
The dynamic programming approach provides an efficient solution with a time complexity of O(n) and a space complexity of O(n) which can be further optimized to O(1). It avoids the exponential time complexity of the naive recursive approach by storing and reusing intermediate results.