The O(n) Club: House Robber, Runtime Errors, and Stealing Like a Pro

The O(n) Club: House Robber, Runtime Errors, and Stealing Like a Pro

⚡ TL;DR

You’re a burglar with commitment issues (no robbing two neighbor-houses). Greedy? Too naive. Brute-force? Welcome to runtime purgatory. Dynamic programming is your cunning friend. Track the max loot stealing (or not) as you shuffle down the street.

// Space-optimized DP. Even your memory will thank you.
int prev1 = 0, prev2 = 0;
for (int n : nums) {
    int grab = n + prev2;
    int skip = prev1;
    int best = Math.max(grab, skip);
    prev2 = prev1;
    prev1 = best;
}
return prev1;

🧠 How Devs Usually Mess This Up

Classic rookie moves include:

• Trying every non-adjacent subset like you’re paid in CPU cycles. That’s O(2^n) — even your laptop’s fan gives up.
• Making recursive calls with no memoization—stack overflow in both Java and your soul.
• Botching base cases: zero houses, one house, two houses. Arrays hate negative indices, and so does production.

🔍 What’s Actually Going On

Picture every house as a chest of loot. For each one, you face a choice: rob it (and skip the previous), or skip it (and dream of better houses ahead). You only need to remember the best outcomes two places back. That’s it. Rolling window, rolling riches. Like a game of musical chairs with fewer criminal charges.

• Grab this house? Add its loot to the best sum up to two houses ago.
• Skip this house? Carry forward yesterday’s best haul.

🛠️ PseudoCode

• If the array is empty, return 0.
  There are no houses—just go home.
• If only one house, grab it and run (return nums[0];).
• If two, pick the richer house.
• For every house after:
• best = max(prev1, nums[i] + prev2)
• Update prev2, prev1 for the next round.
• Return the final prev1.

💻 The Code

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int prev2 = 0;
    int prev1 = 0;
    for (int n : nums) {
        int grab = n + prev2;
        int skip = prev1;
        int best = Math.max(grab, skip);
        prev2 = prev1;
        prev1 = best;
    }
    return prev1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty arrays? Must return 0, not a NullPointerException meltdown.
• House values can be negative (seriously). Don’t assume all loot is good loot.
• Time: O(n), Space: O(1). Basically, speedrun status — no arrays to accidentally index out of bounds.

🧠 Interviewer Brain-Tattoo

Dynamic programming isn’t about hoarding arrays — it’s about remembering just enough to maximize loot (and minimize code regret).