Introduction & Problem Explanation

The House Robber problem describes a scenario where a robber plans to rob houses along a street. Each house has a certain amount of money stashed. However, adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.

Given an integer array nums representing the amount of money in each house, our goal is to determine the maximum amount of money we can rob tonight without alerting the police. For instance, if nums = [2, 7, 9, 3, 1], the optimal choice is to rob house 1 (value 2), house 3 (value 9), and house 5 (value 1), yielding a total of 2 + 9 + 1 = 12. Robbing house 2 (value 7) and house 4 (value 3) only gives 10.

Illustration of House Robber state transitions in Java
Real-World Analogy: The Alternating Security Alarms

Imagine walking down a path of stepping stones. Each stepping stone has a gold coin, but stepping on two adjacent stones sounds a loud siren. At each step, you must make a strategic decision: do you step on the current stone and add its coin to your loot (which means you must have skipped the stone immediately before it), or do you skip the current stone altogether (maintaining the total loot you had at the previous stone)? You dynamically track the best cumulative reward at every step.

The Algorithmic Approach

1. Dynamic Programming (O(n) Time, O(n) Space)

We can define a state array dp, where dp[i] represents the maximum money we can rob from the first i houses. At the i-th house:

  • If we rob house i, we cannot rob house i-1. The max loot is dp[i-2] + nums[i].
  • If we skip house i, the max loot is the same as dp[i-1].
Thus, our recurrence relation is: dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]).

2. Space-Optimized Dynamic Programming (O(n) Time, O(1) Space)

To calculate the result for house i, we only need the results of the last two states (dp[i-1] and dp[i-2]). Instead of keeping a full array, we can use two variables:

  • prev1: The maximum loot from robbing up to the previous house (corresponds to dp[i-1]).
  • prev2: The maximum loot from robbing up to two houses ago (corresponds to dp[i-2]).
As we iterate through each house, we compute the current maximum, then shift prev2 and prev1 forward. This achieves linear runtime with zero extra space overhead.

Step-by-Step Execution Walkthrough

Let's trace the space-optimized algorithm for nums = [2, 7, 9, 3, 1]:

  1. Step 1 (Initialization): Initialize variables representing loot from -1 and -2 houses ago:
    • prev1 = 0
    • prev2 = 0
  2. Step 2 (House 1: val = 2):
    • Determine max: current = Math.max(prev2 + 2, prev1) = Math.max(0 + 2, 0) = 2.
    • Update state: prev2 = prev1 (0), prev1 = current (2).
  3. Step 3 (House 2: val = 7):
    • Determine max: current = Math.max(prev2 + 7, prev1) = Math.max(0 + 7, 2) = 7.
    • Update state: prev2 = 2, prev1 = 7.
  4. Step 4 (House 3: val = 9):
    • Determine max: current = Math.max(prev2 + 9, prev1) = Math.max(2 + 9, 7) = 11.
    • Update state: prev2 = 7, prev1 = 11.
  5. Step 5 (House 4: val = 3):
    • Determine max: current = Math.max(prev2 + 3, prev1) = Math.max(7 + 3, 11) = 11.
    • Update state: prev2 = 11, prev1 = 11.
  6. Step 6 (House 5: val = 1):
    • Determine max: current = Math.max(prev2 + 1, prev1) = Math.max(11 + 1, 11) = 12.
    • Update state: prev2 = 11, prev1 = 12.
  7. Step 7 (Final Result): The loop completes. We return prev1, which is 12.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • int temp = prev1;: Caches the previous house's total loot so it can become the value for "two houses ago" (prev2) in the next step.
  • Math.max(prev2 + num, prev1);: Evaluates the fundamental subproblem choice—should we rob the current house (taking money from two houses ago + current loot) or skip it (taking previous house's total loot)?

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class HouseRobber {

    // Space-Optimized Dynamic Programming: Time O(N), Space O(1)
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int prev1 = 0; // Represents max loot up to house i-1
        int prev2 = 0; // Represents max loot up to house i-2
        
        for (int num : nums) {
            int temp = prev1;
            prev1 = Math.max(prev2 + num, prev1);
            prev2 = temp;
        }
        
        return prev1;
    }

    public static void main(String[] args) {
        HouseRobber solver = new HouseRobber();
        int[] houses = {2, 7, 9, 3, 1};

        System.out.println("--- House Robber Demonstration ---");
        System.out.println("Loot values of houses: " + Arrays.toString(houses));
        int maxLoot = solver.rob(houses);
        System.out.println("Maximum possible loot: " + maxLoot); // Expected: 12
    }
}

Conclusion

The House Robber problem demonstrates the transition from recursive branching to clean, space-optimized dynamic programming. By analyzing state dependencies, we eliminate redundancy and solve the problem in linear O(n) time using only constant O(1) memory.