🏠 House Robber Solution Explained

Github

🔗 View the original problem on LeetCode

🧠 The Big Picture

We have to decide for every house whether to rob it or skip it. Robbing house i means we cannot rob house i-1, so we look two steps back; skipping it means we keep whatever we had until the previous house. Dynamic programming with only two rolling variables (rob1, rob2) is enough.

🔍 Understanding the Variables

rob1
Best up to house i − 2
rob2
Best up to house i − 1

They act like a sliding window of size 2 over the DP table.

rob1
max till i-2
→
rob2
max till i-1
→
i
current house

📝 The Algorithm – Step by Step

function rob(nums) {
    let rob1 = 0;  // best up to i-2
    let rob2 = 0;  // best up to i-1

    for (const num of nums) {
        const temp = Math.max(num + rob1,  // rob current
                              rob2);       // skip current
        rob1 = rob2; // shift window forward
        rob2 = temp;
    }
    return rob2;
}

🎮 Interactive Demo

Trace the array: [5, 1, 2, 10, 6, 2, 7, 9, 3, 1]

rob1: 0
best i-2
rob2: 0
best i-1
Current: -
value at i

Decision Logic:

Click “Next Step” to begin!

💡 Why This Works

🎯 Key Insights