Delete and Earn
What is this problem about?
The Delete and Earn interview question presents a game where you can pick a number nums[i] to earn points equal to its value. However, once you pick nums[i], you must delete all occurrences of nums[i] - 1 and nums[i] + 1 from the array. You can repeat this until no numbers remain. The goal is to maximize the total points earned. This Delete and Earn coding problem is a clever transformation of the "House Robber" problem.
Why is this asked in interviews?
Amazon, Google, and Meta use this to see if a candidate can recognize that a complex-sounding array problem can be reduced to a simpler, well-known DP pattern. It tests your ability to pre-process data into a frequency-weighted sequence where the "non-adjacent" rule applies. It is a high-signal question for Dynamic Programming mastery.
Algorithmic pattern used
This utilizes the Array, Hash Table, Dynamic Programming interview pattern.
- Consolidation: Create an array points where points[v] is the sum of all occurrences of value v in the original array.
- Reduction: Now the rule "delete v-1 and v+1" means you cannot pick adjacent indices in the points array.
- DP Transition: Let dp[i] be the max points using numbers up to value i.
- dp[i] = max(dp[i-1], dp[i-2] + points[i]).
- Space Optimization: You only need the last two values, so O(1) extra space is possible.
Example explanation
nums = [3, 4, 2]
- Points map: {2: 2, 3: 3, 4: 4}.
- Values: 2, 3, 4.
- dp[2]: Earn 2.
- dp[3]: max(dp[2], points[3]) = max(2, 3) = 3. (Since picking 3 deletes 2).
- dp[4]: max(dp[3], dp[2] + points[4]) = max(3, 2 + 4) = 6. (Picking 4 deletes 3, but keeps 2).
Max points: 6.
Common mistakes candidates make
- Greedy approach: Trying to pick the largest numbers first. This fails for cases like [2, 2, 3, 3, 3, 4, 4].
- Inefficient sorting: Trying to solve it by sorting and deleting elements manually (O(N^2)).
- Ignoring zeroes: Not handling the gaps in values if the input array doesn't contain all numbers between min and max.
Interview preparation tip
Always look for ways to map a new problem onto a known one. If you see a rule like "you can't pick the neighbors of X," it is almost always a variation of the Maximum Weight Independent Set on a path graph (House Robber).
