Algorithm Day84 - House Robber

Posted on In , Views:

🧩 Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed.
The only constraint is: adjacent houses cannot be robbed 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.

💬 Examples

Example 1

1
2
3
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) + house 3 (3).

Example 2

1
2
3
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1).

💡 Intuition

This is a dynamic programming problem.
At each house i, you decide to either:

  • Rob it → value = nums[i] + dp[i-2]
  • Skip it → value = dp[i-1]

Transition formula: 

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

🔢 Java Code (DP Optimized)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int prev2 = nums[0];   // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
        
        for (int i = 2; i < nums.length; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

⏱ Complexity Analysis

  • Time: O(n) — one pass through houses.
  • Space: O(1) — only two variables stored.

✍️ Summary

  • A classic DP problem.
  • Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
  • Space can be optimized to O(1).

Related problems

  • lc-213 — House Robber II
  • lc-337 — House Robber III