Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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.
Input:
- An integer array
numswherenums[i]is the money in house i
Output:
- Maximum amount of money that can be robbed
Constraints:
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 400
Examples:
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) then rob house 3 (money = 3).
Total amount = 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 = 2 + 9 + 1 = 12.
Example 3:
Input: nums = [5,1,3,9]
Output: 14
Explanation: Rob house 1 (money = 5) and rob house 4 (money = 9).
Total amount = 5 + 9 = 14.
Solutions
Approach 1: Dynamic Programming with Array
Algorithm:
- For each house, decide whether to rob it or not
- dp[i] = max(rob house i + dp[i-2], don’t rob house i = dp[i-1])
- Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
Python:
def rob_dp_array(nums):
"""
DP solution using array
Time: O(N) - single pass through houses
Space: O(N) - DP array
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
dp = [0] * n
# Base cases
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
# Fill DP table
for i in range(2, n):
# Choice: rob current house + best from i-2, or skip current house
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
return dp[n-1]
def rob_dp_verbose(nums):
"""
Verbose version with detailed explanation
Time: O(N)
Space: O(N)
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
dp = [0] * n
dp[0] = nums[0] # Only one house, rob it
dp[1] = max(nums[0], nums[1]) # Rob the better of first two
print(f"Base cases: dp[0]={dp[0]}, dp[1]={dp[1]}")
for i in range(2, n):
rob_current = nums[i] + dp[i-2] # Rob current + best from 2 houses ago
skip_current = dp[i-1] # Skip current, take best so far
dp[i] = max(rob_current, skip_current)
print(f"House {i}: rob({nums[i]} + {dp[i-2]} = {rob_current}) vs skip({skip_current}) -> {dp[i]}")
return dp[n-1]
# Example usage
print(rob_dp_array([2, 7, 9, 3, 1])) # Output: 12
Java:
class Solution {
/**
* DP solution using array
* Time: O(N)
* Space: O(N)
*/
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int n = nums.length;
int[] dp = new int[n];
// Base cases
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// Fill DP table
for (int i = 2; i < n; i++) {
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
}
return dp[n-1];
}
/**
* Alternative with better variable names
* Time: O(N)
* Space: O(N)
*/
public int robAlternative(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] maxMoney = new int[nums.length];
maxMoney[0] = nums[0];
maxMoney[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int robCurrent = nums[i] + maxMoney[i-2];
int skipCurrent = maxMoney[i-1];
maxMoney[i] = Math.max(robCurrent, skipCurrent);
}
return maxMoney[nums.length - 1];
}
}
Go:
// rob - DP solution using array
// Time: O(N)
// Space: O(N)
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
n := len(nums)
dp := make([]int, n)
// Base cases
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
// Fill DP table
for i := 2; i < n; i++ {
dp[i] = max(nums[i]+dp[i-2], dp[i-1])
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
JavaScript:
/**
* DP solution using array
* Time: O(N)
* Space: O(N)
*/
function rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const n = nums.length;
const dp = new Array(n);
// Base cases
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// Fill DP table
for (let i = 2; i < n; i++) {
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
}
return dp[n-1];
}
C#:
public class Solution {
/// <summary>
/// DP solution using array
/// Time: O(N)
/// Space: O(N)
/// </summary>
public int Rob(int[] nums) {
if (nums.Length == 0) return 0;
if (nums.Length == 1) return nums[0];
int n = nums.Length;
int[] dp = new int[n];
// Base cases
dp[0] = nums[0];
dp[1] = Math.Max(nums[0], nums[1]);
// Fill DP table
for (int i = 2; i < n; i++) {
dp[i] = Math.Max(nums[i] + dp[i-2], dp[i-1]);
}
return dp[n-1];
}
}
Approach 2: Space Optimized DP
Since we only need the last two values, optimize space to O(1).
Python:
def rob_optimized(nums):
"""
Space-optimized DP solution
Time: O(N) - single pass
Space: O(1) - only two variables
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# prev2 = dp[i-2], prev1 = dp[i-1]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
current = max(nums[i] + prev2, prev1)
prev2 = prev1
prev1 = current
return prev1
def rob_optimized_clean(nums):
"""
Clean space-optimized version
Time: O(N)
Space: O(1)
"""
prev_rob = prev_not_rob = 0
for money in nums:
# Current max if we rob this house
curr_rob = prev_not_rob + money
# Current max if we don't rob this house
curr_not_rob = max(prev_rob, prev_not_rob)
prev_rob, prev_not_rob = curr_rob, curr_not_rob
return max(prev_rob, prev_not_rob)
# Example usage
print(rob_optimized([2, 7, 9, 3, 1])) # Output: 12
Java:
class Solution {
/**
* Space-optimized DP solution
* Time: O(N)
* Space: O(1)
*/
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prev2 = nums[0];
int prev1 = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int current = Math.max(nums[i] + prev2, prev1);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/**
* Alternative clean approach
* Time: O(N)
* Space: O(1)
*/
public int robClean(int[] nums) {
int prevRob = 0; // Max money if we robbed previous house
int prevNotRob = 0; // Max money if we didn't rob previous house
for (int money : nums) {
int currRob = prevNotRob + money; // Rob current house
int currNotRob = Math.max(prevRob, prevNotRob); // Skip current house
prevRob = currRob;
prevNotRob = currNotRob;
}
return Math.max(prevRob, prevNotRob);
}
}
Key Insights
- State Definition: dp[i] represents the maximum money that can be robbed up to house i
- Recurrence Relation: dp[i] = max(rob house i + dp[i-2], skip house i = dp[i-1])
- Space Optimization: Only need last two states, can reduce to O(1) space
- Choice at Each Step: Either rob current house or skip it
- Optimal Substructure: Optimal solution contains optimal solutions to subproblems
Edge Cases
- Empty array: Return 0
- Single house: Rob it (return nums[0])
- Two houses: Rob the one with more money
- All zeros: Return 0
- Alternating pattern: Should rob every other house optimally
Test Cases
def test_house_robber():
test_cases = [
([1, 2, 3, 1], 4),
([2, 7, 9, 3, 1], 12),
([5, 1, 3, 9], 14),
([1], 1),
([1, 2], 2),
([2, 1, 1, 2], 4),
([0, 0, 0], 0)
]
for nums, expected in test_cases:
result = rob_optimized(nums)
assert result == expected, f"nums={nums}, expected={expected}, got={result}"
print(f"nums={nums} -> {result} ✓")
test_house_robber()
Common Mistakes
- Wrong base cases: Not handling edge cases for small arrays
- Index errors: Accessing dp[i-2] when i < 2
- Greedy approach: Thinking every other house should be robbed
- Not considering skip option: Forgetting that skipping might be optimal
- Space complexity: Not optimizing from O(N) to O(1) when possible
Follow-up Questions
- House Robber II: Houses arranged in a circle (can’t rob first and last)
- House Robber III: Houses arranged as a binary tree
- Path reconstruction: Return which houses to rob, not just maximum amount
- Multiple constraints: Additional constraints on robbing patterns
- Variant costs: Different costs for robbing different types of houses
Interview Tips
- Start with brute force: Explain recursive approach first
- Identify overlapping subproblems: Show why DP is needed
- Build up solution: Array DP first, then space optimization
- Walk through examples: Trace through the algorithm step by step
- Handle edge cases: Make sure to test small inputs
- Discuss time/space tradeoffs: Compare different approaches
- Code incrementally: Start with basic solution, then optimize