📊 Interactive Guide: The House Robber Problem

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 array of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example:

Input: [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9), rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Enter house values (comma-separated integers):

Interactive Visualization

Click the buttons below to step through the algorithm or use the slider to control speed in auto mode.

Click “Next Step” to start the algorithm.

Dynamic Programming Table

This table shows the maximum amount we can rob up to a certain house:

Understanding the Algorithm

Key Insight

The crucial insight is that for each house, we have two options:

Rob this house: If we rob the current house, we can’t rob the previous one. So we add the current house’s value to the maximum amount we could rob from houses before the previous one.
Skip this house: If we skip the current house, the maximum amount remains the same as what we could rob from all previous houses.

For each house at position i, the maximum amount we can rob is:

dp[i] = max(dp[i-2] + nums[i], dp[i-1])

Where:

dp[i] = Maximum amount we can rob up to house i
nums[i] = Amount of money in house i

Time & Space Complexity

Time Complexity: O(n) Space Complexity: O(n) or O(1)

We only need to iterate through the array once, giving us O(n) time complexity. For space, the DP array gives us O(n), but it’s possible to optimize to O(1) by just keeping track of the previous two maximum values.

Implementation in JavaScript

/**
 * @param {number[]} nums - Array of house values
 * @return {number} - Maximum amount that can be robbed
 */
function rob(nums) {
  // Handle edge cases
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  // Initialize dp array
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  
  // Fill dp array
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
  }
  
  // Return maximum amount
  return dp[nums.length - 1];
}

Optimized Solution (O(1) space)

/**
 * @param {number[]} nums - Array of house values
 * @return {number} - Maximum amount that can be robbed
 */
function robOptimized(nums) {
  // Handle edge cases
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  // Initialize variables to track previous two max values
  let prevMax = nums[0];
  let currMax = Math.max(nums[0], nums[1]);
  
  // Iterate through houses starting from the third
  for (let i = 2; i < nums.length; i++) {
    const temp = currMax;
    currMax = Math.max(currMax, prevMax + nums[i]);
    prevMax = temp;
  }
  
  // Return maximum amount
  return currMax;
}

Common Variations & Extensions

House Robber II: Houses are arranged in a circle, so the first and last houses are adjacent.
House Robber III: Houses are arranged in a binary tree structure.
Staggered Pattern: Similar problems like maximum sum of non-adjacent elements.

Key Takeaways

The House Robber problem is a classic dynamic programming problem that teaches optimal substructure.
For each house, we decide whether to robit or not to maximize our total.
We can solve it using a DP array where dp[i] represents the maximum amount we can rob up to house i.
The space complexity can be optimized from O(n) to O(1) by just tracking the previous two maximum values.
This pattern of "taking or skipping" elements appears in many other dynamic programming problems.

House robbing algorithm