House Robber

This one looks simple. A row of houses, each holds some money, grab the most you can. But there is a catch. You cannot rob two houses that sit next to each other. So the interviewer is not testing if you can add numbers. They are testing if you can spot the choice hidden at every step. At each house you decide. Do I take this one, or do I skip it? That small decision is the whole problem.

🏠 The Problem

You are given an array. Each number is the money in one house. You are a robber walking down the street. If you rob two houses that are adjacent, the alarm goes off. So you must skip at least one house between any two you rob. Find the most money you can take.

Input:  [2, 7, 9, 3, 1]
Output: 12

Explanation: rob house 0 (2) + house 2 (9) + house 4 (1) = 12.
You cannot do 2 + 7 because those houses touch.

So at every house there is a yes-or-no decision. And the decisions are linked. That linking is what makes it interesting.

🤔 The Brute Force Idea

The first thought most people have is to try every possible set of houses that has no two neighbours. Then pick the biggest sum. You can do this with recursion. At each house you split into two paths. One path robs the house and jumps two ahead. The other path skips the house and moves one ahead.

That works, but it is slow. Each house splits into two paths. So the number of paths grows roughly like 2 to the power of n. For a long street this explodes. The same smaller streets get solved again and again. We are wasting work.

💡 The Optimal Idea: Dynamic Programming

Here is the key thought. The most money you can rob from the first i houses depends only on smaller answers you already found. So you do not need to recompute anything. You build the answer house by house.

Stand at house i. You have two options.

• Skip this house. Then your best is whatever you had at house i - 1.
• Rob this house. Then you get its money plus your best from house i - 2, because house i - 1 is now off-limits.

You take the bigger of the two. In words, the recurrence is:

best[i] = max(best[i - 1], money[i] + best[i - 2])

Let us walk it on [2, 7, 9, 3, 1].

house 0:  best = 2                        -> 2
house 1:  max(2, 7)        = 7            -> 7
house 2:  max(7, 2 + 9)    = max(7, 11)  -> 11
house 3:  max(11, 7 + 3)   = max(11, 10) -> 11
house 4:  max(11, 11 + 1)  = max(11, 12) -> 12

The answer is 12. See how each line only looks at the two lines before it?

Now notice something. To compute the answer at house i, you only ever need the last two answers. You do not need the whole table. So you can throw away everything older and keep just two rolling variables. That drops the extra memory from O(n) down to O(1).

Steps to solve it

1. Keep two variables. prev2 is the best up to two houses back. prev1 is the best up to the house just before.
2. Start both at 0, because before any house there is no money.
3. Walk through each house. Compute take = money + prev2 and skip = prev1.
4. The new best for this house is the bigger of take and skip.
5. Slide the window forward. prev2 becomes the old prev1, and prev1 becomes the new best.
6. After the last house, prev1 holds the answer.

#include <stdio.h>

// Returns the most money we can rob without touching adjacent houses.
int rob(int money[], int n) {
    int prev2 = 0; // best up to two houses back
    int prev1 = 0; // best up to the previous house
    for (int i = 0; i < n; i++) {
        int take = money[i] + prev2;     // rob this house
        int skip = prev1;                // leave this house
        int best = take > skip ? take : skip;
        prev2 = prev1;                   // slide the window forward
        prev1 = best;
    }
    return prev1;
}

int main(void) {
    int houses[] = {2, 7, 9, 3, 1};
    int n = sizeof(houses) / sizeof(houses[0]);
    printf("Max money robbed: %d\n", rob(houses, n));
    return 0;
}

Max money robbed: 12

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Returns the most money we can rob without touching adjacent houses.
int rob(const vector<int>& money) {
    int prev2 = 0; // best up to two houses back
    int prev1 = 0; // best up to the previous house
    for (int m : money) {
        int take = m + prev2;            // rob this house
        int skip = prev1;                // leave this house
        int best = max(take, skip);
        prev2 = prev1;                   // slide the window forward
        prev1 = best;
    }
    return prev1;
}

int main() {
    vector<int> houses = {2, 7, 9, 3, 1};
    cout << "Max money robbed: " << rob(houses) << endl;
    return 0;
}

Max money robbed: 12

public class HouseRobber {
    // Returns the most money we can rob without touching adjacent houses.
    static int rob(int[] money) {
        int prev2 = 0; // best up to two houses back
        int prev1 = 0; // best up to the previous house
        for (int m : money) {
            int take = m + prev2;            // rob this house
            int skip = prev1;                // leave this house
            int best = Math.max(take, skip);
            prev2 = prev1;                   // slide the window forward
            prev1 = best;
        }
        return prev1;
    }

    public static void main(String[] args) {
        int[] houses = {2, 7, 9, 3, 1};
        System.out.println("Max money robbed: " + rob(houses));
    }
}

Max money robbed: 12

# Returns the most money we can rob without touching adjacent houses.
def rob(money):
    prev2 = 0  # best up to two houses back
    prev1 = 0  # best up to the previous house
    for m in money:
        take = m + prev2     # rob this house
        skip = prev1         # leave this house
        best = max(take, skip)
        prev2 = prev1        # slide the window forward
        prev1 = best
    return prev1


houses = [2, 7, 9, 3, 1]
print("Max money robbed:", rob(houses))

Max money robbed: 12

// Returns the most money we can rob without touching adjacent houses.
function rob(money) {
  let prev2 = 0; // best up to two houses back
  let prev1 = 0; // best up to the previous house
  for (const m of money) {
    const take = m + prev2;        // rob this house
    const skip = prev1;            // leave this house
    const best = Math.max(take, skip);
    prev2 = prev1;                 // slide the window forward
    prev1 = best;
  }
  return prev1;
}

const houses = [2, 7, 9, 3, 1];
console.log("Max money robbed:", rob(houses));

Max money robbed: 12

⏱️ Time and Space Complexity

🧩 Key Takeaways

• ✅ At every house you make one choice. Rob it and add the best from two houses back, or skip it and keep the best from the previous house.
• ✅ The recurrence is best[i] = max(best[i - 1], money[i] + best[i - 2]).
• ✅ You only need the last two answers, so two rolling variables are enough. That gives O(1) extra space.
• ✅ Start both variables at 0 so the empty street and the first house work without special cases.
• ✅ The whole thing runs in O(n) time with a single pass.

🚀 What’s Next?

• Climbing Stairs
• Coin Change