The O(n) Club: Delete and Earn – When House Robber Goes Full Arcade

The O(n) Club: Delete and Earn – When House Robber Goes Full Arcade

⚡ TL;DR

Every time you delete a number, you also assassinate its neighbors—like arcade Pac-Man but with fewer ghosts, more regrets. The smart move? Stop brute-forcing and use dynamic programming the House Robber way on number values, not array indices.

// Java: It's basically House Robber, trust me
public int deleteAndEarn(int[] nums) {
    int max = 0;
    for (int n : nums) max = Math.max(max, n);
    int[] points = new int[max + 1];
    for (int n : nums) points[n] += n;
    int take = 0, skip = 0;
    for (int val : points) {
        int temp = Math.max(take, skip);
        take = skip + val;
        skip = temp;
    }
    return Math.max(take, skip);
}

🧠 How Devs Usually Mess This Up

If you tried recursion, stop—your CPU is already crying.
Common train wrecks include:

• Not deleting neighbors: Nope, you don’t just remove the picked guy. You vaporize all copies of n, n-1, and n+1 like a poorly-planned bug-fix.
• Missing the House Robber pattern: If you didn’t realize adjacency is about values, not array spots, congratulations on writing a five-nested-loop monster.
• Ignoring duplicates: Nailing each ‘3’ separately? Even brute force wants a refund.

🔍 What’s Actually Going On

Imagine every unique number as its own loot box. To smash a box (delete and earn), you have to skip the boxes right before and after it—no double-dipping. Instead of iterating the array wildly, you:

• Sum up all loot for each box label (number), e.g., all ‘4’s = 4 * count of 4.
• Walk through loot, choosing to take or skip each box—classic “rob or pass” dilemma.
• Your reward is the highest total in these parallel universes of temptation.

And there you have it. It’s House Robber, but your neighbors are numbers, not addresses.

🛠️ PseudoCode

• 1. Collect loot for each number

  int[] points = new int[maxNum + 1];
  for (int n : nums) points[n] += n;

  Think: points[5] holds the total for all 5s.
• 2. Plan the heist with DP

  take = 0; skip = 0;
  for (val : points) {
    temp = Math.max(take, skip);
    take = skip + val;
    skip = temp;
  }

  Take means robbing this ‘house’, skip means chilling till the next round.
• 3. Collect your loot — Return the higher of take or skip when you’re done. 🍯

💻 The Code

// Clean Java DP: skip recursion, get points
public int deleteAndEarn(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int max = 0;
    for (int n : nums) max = Math.max(max, n);
    int[] points = new int[max + 1];
    for (int n : nums) points[n] += n;
    int take = 0, skip = 0;
    for (int val : points) {
        int temp = Math.max(take, skip);
        take = skip + val;
        skip = temp;
    }
    return Math.max(take, skip);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Array size blow-up: Huge values in nums? Your memory usage will go brrr. (And, possibly, down.)
• Empty input: Remember to check for nums.length == 0 or you’ll debug till lunchtime.
• Forgot to aggregate: If you try processing nums raw, you miss the actual DP juice.
• Time/Space reality: O(N + K), N = array size, K = max num; fast unless the interviewer is messing with you.

🧠 Interviewer Brain-Tattoo

“Every time you see ‘delete the neighbors’, just whisper ‘House Robber in disguise’ and save yourself 30 minutes of existential recursion.”