198. House Robber

← All Problems
medium Dynamic Programming
Given an integer array nums where each element represents the amount of money in a house, return the maximum amount you can rob tonight. The constraint is that you cannot rob two adjacent houses, since they have connected security systems. In other words, if you rob house i, you cannot rob house i-1 or i+1.

Example

nums = [2, 7, 9, 3, 1]

Output: 12

Rob houses 0, 2, and 4 for a total of 2 + 9 + 1 = 12. No two of these houses are adjacent, and no other combination yields more.

At each house, you have two choices: rob it and add its value to what you had two houses ago (dp[i-2]), or skip it and keep what you had at the previous house (dp[i-1]). Take whichever is larger. You only need two variables since each decision depends on the last two results.

Why this works

You can never rob two adjacent houses, so at each house you face a simple choice: rob it (adding its value to the best you could do two houses ago) or skip it (keeping the best from the previous house). By carrying forward just the last two best totals, you always have enough information to make the optimal decision.

Step by step

  1. Initialize two variables — prev2 and prev1 both start at 0, representing the best loot from “two houses back” and “one house back.”
  2. Visit each house — compute curr = max(prev1, prev2 + num). This asks: “Is it better to skip this house or rob it?”
  3. Slide the window forward — shift prev2 = prev1 and prev1 = curr so the next iteration has fresh “two back” and “one back” values.
  4. Return prev1 — after processing all houses, prev1 holds the maximum total loot.
Time: O(n) Space: O(1) 
class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int curr = Math.max(prev1, prev2 + num); // skip this house OR rob it + best from two back
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int curr = max(prev1, prev2 + num); // skip this house OR rob it + best from two back
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

def rob(nums: list[int]) -> int:
    prev2, prev1 = 0, 0  # best totals ending two houses back and one house back
    for num in nums:
        curr = max(prev1, prev2 + num)  # skip this house OR rob it + best from two back
        prev2 = prev1
        prev1 = curr
    return prev1