Delete and Earn: House Robber in Disguise

At first glance, LeetCode 740: Delete and Earn looks like a new kind of problem. You pick a number, earn its value, and delete all neighbors. But once you see the trick, this is House Robber wearing a different outfit. The "delete neighbors" rule maps directly to the "can't rob adjacent houses" constraint. Spot the reduction, and the rest writes itself.

The problem

You are given an integer array nums. In one operation, you pick any nums[i], earn nums[i] points, and then delete every element equal to nums[i] - 1 or nums[i] + 1 from the array. You can perform this operation as many times as you want. Return the maximum number of points you can earn.

The key insight: if you decide to take a value like 3, you must take all the 3s (since they are still available and free points), but you lose every 2 and every 4. That means choosing value v is incompatible with choosing v - 1 or v + 1. Sound familiar?

The approach

The solution has two parts:

1. Group and sum. Build an array earn where earn[v] is the total points you get from taking all copies of value v. For example, if nums contains three 3s, then earn[3] = 9.

2. Run House Robber. Once you have the earn array, the problem is identical to House Robber. You walk through values 1 through max(nums), and at each value you decide: take it (earn earn[v] but skip v - 1) or skip it (keep whatever you had from v - 1). The recurrence is dp[v] = max(dp[v-1], dp[v-2] + earn[v]), which is exactly the rob-or-skip decision from House Robber.

Since you only need the previous two values, you can use two variables instead of a full array, bringing space down to O(1) beyond the earn array itself.

def delete_and_earn(nums: list[int]) -> int:
    max_val = max(nums)
    earn = [0] * (max_val + 1)
    for num in nums:
        earn[num] += num

    prev, curr = 0, 0
    for i in range(1, max_val + 1):
        prev, curr = curr, max(curr, prev + earn[i])
    return curr

Step-by-step walkthrough

Let's trace through nums = [2, 2, 3, 3, 3, 4] to see exactly how the grouping and DP play out.

The answer is 9: you take all the 3s (earning 9 points) and skip the 2s and 4s. Taking the 2s and 4s together would only give you 4 + 4 = 8, which is worse. The DP figures this out automatically by comparing "take" versus "skip" at each value.

Complexity analysis

Time: You make one pass through nums to build the earn array (O(n)), then one pass from 1 to max_val to run the DP (O(k)). The total is O(n + k).

Space: The earn array is size k + 1. The DP itself uses only two variables. If the max value in nums is very large relative to the number of elements, you could use a hash map instead of an array to avoid allocating sparse entries, but for most inputs the array approach is cleaner.

The building blocks

Reducing to a known problem

The hardest part of Delete and Earn is not the DP itself. It is recognizing that the problem reduces to House Robber. Once you see that "taking value v eliminates v-1 and v+1" maps to "robbing house i eliminates house i-1 and i+1," you can reuse the exact same recurrence and space optimization.

This pattern of reduction shows up throughout competitive programming and interviews. The problem disguises itself as something novel, but under the surface it is a known problem you have already solved. The skill is in stripping away the surface details to find the underlying structure.

Here is a mental checklist for spotting reductions: What choices am I making? What does each choice prevent me from doing? If choosing option A blocks the "adjacent" options, you are probably looking at a House Robber variant. If choosing option A contributes a cost that depends on remaining subproblems, you might be looking at a knapsack or interval scheduling variant.

The more problems you solve, the faster you recognize these patterns. Delete and Earn is a great example because the reduction is clean and complete. There is no extra twist or edge case beyond the mapping itself.

Edge cases

• All elements the same: e.g., [5, 5, 5]. There are no adjacent values to conflict with, so you take them all. earn[5] = 15, answer is 15.

• Single element: [7]. Only one value, take it. Answer is 7.

• Two adjacent values: e.g., [2, 3, 3]. earn[2] = 2, earn[3] = 6. You pick the 3s for 6 points. The DP handles this automatically.

• Large gaps between values: e.g., [1, 1, 100, 100]. Values 1 and 100 are not adjacent, so you can take both. The DP walks through values 1 to 100, but most earn entries are zero and do not affect the result. Answer is 2 + 200 = 202.

From understanding to recall

You have just seen how Delete and Earn reduces to House Robber, and the logic probably clicks right now. But recognizing this reduction under interview pressure, when nobody tells you it is House Robber in disguise, is a different skill entirely.

Spaced repetition helps you bridge that gap. You revisit the problem at increasing intervals, practice the reduction from scratch each time, and eventually the pattern recognition becomes automatic. Seeing "pick a value, lose its neighbors" will immediately trigger "this is House Robber on values" without any conscious effort.

Problem reduction is one of the most powerful techniques in your toolkit. Drilling it with specific examples like Delete and Earn builds the intuition that transfers to problems you have never seen before.

Related posts

• House Robber - The foundational problem that Delete and Earn reduces to
• Climbing Stairs - The simplest DP problem with the same recurrence structure
• Coin Change - Another DP problem about making optimal choices