Delete and Earn — Disguised House Robber on a Value Array

Problem Statement#

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times: Pick any nums[i], delete it to earn nums[i] points, and also delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1. Return the maximum number of points you can earn by applying the above operation some number of times.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^4

Example 1:

Input:  nums = [3, 4, 2]
Output: 6
Explanation: Delete 4 to earn 4 points (also deletes 3).
             Then delete 2 to earn 2 points. Total = 6.
             Alternatively, delete 3 earns 3 (deletes 2 and 4). Total = 3. So 6 is better.

Example 2:

Input:  nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: Delete 3 three times to earn 3 * 3 = 9 points.
             Deleting 3 forces deletion of all 2s and all 4s.

Example 3:

Input:  nums = [1, 1, 1, 2, 4, 5, 5]
Output: 13
Explanation: Delete all 1s (earn 3, deletes all 2s).
             Delete all 5s (earn 10, deletes all 4s). Total = 13.

Why This Problem Matters#

Delete and Earn (LeetCode 740) is a classic "disguised DP" problem that tests pattern recognition above all else. On the surface it reads like a simulation or game problem. Underneath, it is House Robber (LC 198) with a preprocessing step. Recognizing that connection is the entire insight — once you see it, the solution is straightforward. Without it, candidates spiral into backtracking or greedy approaches that quickly fail.

Amazon and Meta use this problem in interviews because it assesses whether candidates look past surface-level descriptions to structural patterns. A candidate who says "this looks like House Robber after collapsing values into an earn array" earns immediate credibility. One who tries to simulate the deletion process runs into exponential complexity.

The problem also reinforces two important habits: always summarize value frequencies before running DP, and always ask "which known DP pattern does this resemble?"

The Core Insight#

When you choose to earn points from value v, you earn v * count(v) total (all copies of v are deleted and you earn v for each). But you can never also earn from value v-1 or value v+1 — they are all deleted.

This is exactly the House Robber constraint: if you "rob" value v, you cannot "rob" values v-1 or v+1.

Reduction:

1. Build an earn array indexed by value: earn[v] = v * count(v).
2. Apply House Robber DP on the earn array: dp[v] = max(dp[v-1], dp[v-2] + earn[v]).
3. Return dp[max_val].

Optimal substructure: the maximum points from values up to v depends only on the answers for v-1 and v-2.

Overlapping subproblems: naive recursion recomputes the same value states many times.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion on value range, illustrative only
def deleteAndEarn(nums):
    max_val = max(nums)
    earn = [0] * (max_val + 1)
    for v in nums:
        earn[v] += v
 
    def dp(v):
        if v <= 0:
            return 0
        if v == 1:
            return earn[1]
        return max(dp(v - 1), dp(v - 2) + earn[v])
 
    return dp(max_val)

// JavaScript — naive recursion
function deleteAndEarn(nums) {
    const maxVal = Math.max(...nums);
    const earn = new Array(maxVal + 1).fill(0);
    for (const v of nums) earn[v] += v;
 
    function dp(v) {
        if (v <= 0) return 0;
        if (v === 1) return earn[1];
        return Math.max(dp(v - 1), dp(v - 2) + earn[v]);
    }
 
    return dp(maxVal);
}

Exponential time due to repeated recomputation of the same v states.

Step 2 — Top-Down Memoization (O(max_val) time, O(max_val) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        max_val = max(nums)
        earn = [0] * (max_val + 1)
        for v in nums:
            earn[v] += v
 
        @lru_cache(maxsize=None)
        def dp(v: int) -> int:
            if v <= 0:
                return 0
            if v == 1:
                return earn[1]
            return max(dp(v - 1), dp(v - 2) + earn[v])
 
        return dp(max_val)

// JavaScript — top-down memoization
var deleteAndEarn = function(nums) {
    const maxVal = Math.max(...nums);
    const earn = new Array(maxVal + 1).fill(0);
    for (const num of nums) earn[num] += num;
 
    const memo = new Map();
    function dp(v) {
        if (v <= 0) return 0;
        if (v === 1) return earn[1];
        if (memo.has(v)) return memo.get(v);
        const result = Math.max(dp(v - 1), dp(v - 2) + earn[v]);
        memo.set(v, result);
        return result;
    }
 
    return dp(maxVal);
};

Step 3 — Bottom-Up Tabulation (O(max_val) time, O(max_val) space)#

# Python — bottom-up tabulation
class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        max_val = max(nums)
        earn = [0] * (max_val + 1)
        for v in nums:
            earn[v] += v
 
        if max_val == 1:
            return earn[1]
 
        dp = [0] * (max_val + 1)
        dp[1] = earn[1]
        for v in range(2, max_val + 1):
            dp[v] = max(dp[v - 1], dp[v - 2] + earn[v])
 
        return dp[max_val]

// JavaScript — bottom-up tabulation
var deleteAndEarn = function(nums) {
    const maxVal = Math.max(...nums);
    const earn = new Array(maxVal + 1).fill(0);
    for (const num of nums) earn[num] += num;
 
    if (maxVal === 1) return earn[1];
 
    const dp = new Array(maxVal + 1).fill(0);
    dp[1] = earn[1];
    for (let v = 2; v <= maxVal; v++) {
        dp[v] = Math.max(dp[v - 1], dp[v - 2] + earn[v]);
    }
 
    return dp[maxVal];
};

Optimized Solution#

Compress the dp array to two rolling variables — identical to the House Robber space optimization:

# Python — space-optimized, O(max_val) time, O(max_val) space for earn, O(1) extra DP space
class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        max_val = max(nums)
        earn = [0] * (max_val + 1)
        for v in nums:
            earn[v] += v
 
        prev2, prev1 = 0, 0
        for e in earn:
            prev2, prev1 = prev1, max(prev1, prev2 + e)
        return prev1

// JavaScript — space-optimized
var deleteAndEarn = function(nums) {
    const maxVal = Math.max(...nums);
    const earn = new Array(maxVal + 1).fill(0);
    for (const num of nums) earn[num] += num;
 
    let prev2 = 0, prev1 = 0;
    for (const e of earn) {
        [prev2, prev1] = [prev1, Math.max(prev1, prev2 + e)];
    }
 
    return prev1;
};

The earn array itself is O(max_val) — the dominant space cost. The DP portion uses only O(1) extra space.

Visual Dry Run#

Input: nums = [2, 2, 3, 3, 3, 4], max_val = 4

Build earn array:

House Robber DP on earn:

Answer: 9. We picked value 3 (earn 9), which deleted all 2s and 4s.

Complexity Analysis#

Note: max_val can be up to 10^4, so even the naive earn array construction is fast in practice.

Common Mistakes#

1. Building earn as earn[v] = v instead of earn[v] = v * count(v). The total points from value v is v times the number of occurrences. If you set earn[v] = v, you earn only one copy's worth and miss the rest.

2. Iterating only over unique sorted values and checking consecutiveness. Some candidates sort unique values and compare adjacent pairs. This works but is error-prone — gaps between non-consecutive values (e.g., values 1 and 5) need special handling. Using a fixed-size earn array indexed by value is simpler and more reliable.

3. Starting the DP from index 0. Values start at 1 per constraints. earn[0] is always 0. If you initialize prev2, prev1 = earn[0], earn[1] you may be starting the rolling window incorrectly. Initialize both to 0 and iterate over the full earn array from index 0.

4. Forgetting to handle max_val = 1. When all values are 1, the answer is earn[1]. The rolling variable solution handles this naturally.

5. Confusing the earn array index with the nums array index. The earn array is indexed by value (up to 10^4), not by position in nums (up to 2*10^4). Keep these two spaces separate in your mind.

6. Using a greedy approach. Always picking the highest-earn value does not always work. Counter-example: earn = [0, 5, 6]. Greedy picks 6 (skips 5). But picking both 1 and... wait, they are adjacent. Picks only 6 = 6. Greedy also gives 6. A subtler counter: earn = [0, 3, 4, 5]. Greedy picks 5 (v=3). But max(dp[2], dp[1]+earn[3]) = max(4, 3+5) = 8. So picking values 1 (earn 3) and 3 (earn 5) totals 8, which the DP finds correctly.

Interview Tips#

Lead with the reduction. The very first thing to say: "I notice that choosing value v prevents choosing v-1 and v+1 — that is the skip-adjacent constraint from House Robber. After precomputing earn[v] = v * count(v), this becomes House Robber on the earn array."

Show the preprocessing step explicitly. Build the earn array before touching the DP. This demonstrates separation of concerns: data transformation first, then DP logic.

Mention the connection to House Robber. Say: "After the reduction, the earn array plays the role of nums in House Robber, and skipping adjacent values is the same as skipping adjacent houses."

State the complexity clearly. "Time is O(n + max_val) — O(n) to build the earn array and O(max_val) for the DP. Space is O(max_val) for the earn array, with O(1) extra for the rolling variables."

Follow-up Questions#

Q: What if values can be up to 10^9? The fixed-size earn array becomes too large. Instead, sort the unique values, then iterate through them in order, running a modified House Robber that checks whether consecutive unique values differ by 1 (adjacent, so they conflict) or more (non-adjacent, so both can be taken freely).

Q: What if picking value v also deletes values within radius r (not just ±1)? Change the recurrence to dp[v] = max(dp[v-1], dp[v-r-1] + earn[v]). Keep r+1 rolling variables instead of 2.

Q: What if you can pick the same value at most k times? Modify the earn array: earn[v] = v * min(count(v), k). The DP is unchanged.

Q: What if you want to output which values you picked? Track a decision array and reconstruct backward: if dp[v] == dp[v-1], you skipped v; otherwise you took it and earn[v] contributed.

Q: Can you solve this without an explicit earn array? Yes — sort the input and accumulate points for consecutive equal values on the fly, applying the House Robber logic when you move to the next distinct value. This saves memory when values are sparse, but the code is more complex.

Key Takeaways#

• The critical insight: choosing value v earns v * count(v) and blocks v-1 and v+1 — this is exactly the House Robber skip-adjacent constraint.
• Precompute earn[v] = v * count(v) for all values 0 through max_val, then run House Robber DP on the earn array.
• The recurrence dp[v] = max(dp[v-1], dp[v-2] + earn[v]) is identical to House Robber, with earn replacing nums.
• Space-optimize with two rolling variables iterating over the earn array.
• The ability to recognize a "disguised" DP — where the surface description hides a known pattern — is one of the most valuable interview skills. Train this by always asking "what DP problem does this remind me of?"
• This problem and House Robber share a pattern family: Delete and Earn, House Robber, House Robber II, and scheduling problems all use skip-adjacent DP.