Code Logo

House Robber

Published at24 Jul 2026
Created by
Medium 0 views
Like0

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 that adjacent houses have security systems that will alert the police if two adjacent houses are broken into on the same night. Given an array of money amounts, return the maximum amount you can rob without alerting the police.

This is a classic DP problem where the decision at each house depends on whether we robbed the previous house. The recurrence is: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Either skip the current house (keep the maximum from the previous house) or rob it (add its money to the maximum from two houses ago).

The base cases are dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]). The space can be optimized to O(1) using two variables instead of an array, since each decision only depends on the two previous results. The time complexity is O(n).

Edge cases include an empty array (return 0), a single house (return its value), and two houses (return the larger one).

The house robber recurrence illustrates the fundamental DP concept of choosing between two options at each step: include or exclude. The optimal substructure property ensures that the best decision at each house depends only on the previous two subproblem results, enabling the O(1) space optimization.

Example Input & Output

Example 1
Input
[1]
Output
1
Explanation

Single house.

Example 2
Input
[]
Output
0
Explanation

Empty array.

Example 3
Input
[2,1]
Output
2
Explanation

Only rob the first house.

Example 4
Input
[1,2,3,1]
Output
4
Explanation

Rob house 1 (1) and 3 (3). Total = 4.

Example 5
Input
[2,7,9,3,1]
Output
12
Explanation

Rob house 1 (2), 3 (9), 5 (1) = 12.

Algorithm Flow

Recommendation Algorithm Flow for House Robber
Recommendation Algorithm Flow for House Robber

Solution Approach

DP with two rolling variables. For each house, compute max of robbing it or skipping it.

function solution(nums) {
  var a = 0, b = 0;
  for (var i = 0; i < nums.length; i++) {
    var c = Math.max(a + nums[i], b);
    a = b;
    b = c;
  }
  return b;
}

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

Best Answers

java
class Solution {
    public int solution(int[] nums) {
        int a = 0, b = 0;
        for (int n : nums) {
            int c = Math.max(a + n, b);
            a = b;
            b = c;
        }
        return b;
    }
}