DP — Delete and Earn
↗ LeetCode: Delete and Earn · Medium · pattern chapter →
Delete x to earn x points; also removes all x-1 and x+1. Max points.
Example 1 — nums=[3,4,2] → 6Example 2 — nums=[2,2,3,3,3,4] → 9Example 3 — nums=[1,1,1,2,4,5,5,5,6] → 18
Constraints — 1 ≤ n ≤ 2·10⁴; 1 ≤ nums[i] ≤ 10⁴. Brute subset enumeration is 2ⁿ — impossible past n=25. Reduction to House Robber gives O(n + max) ≈ 4·10⁴. Brute enumerates 2ⁿ subsets — at n=2·10⁴ = 10⁶⁰⁰⁰ (dead). Reduce to house-robber on bucketed sums → DP O(n + max) = 2·10⁴ + 10⁴ = 3·10⁴ ops = <2 ms.
Interview timer00:00
Approach 1 — Brute subset enumeration
Intuition. For each subset of values in nums, check if any two are adjacent (differ by 1). If not, sum the values. Track max.
Complexity — Time O(2ⁿ · n); Space O(n). TLE past n=20. In an interview say "the 'adjacent-value taboo' has the same structure as House Robber → O(n + max)."
Approach 2 — Reduce to House Robber (canonical)
Insight. Bucket totals: points[v] = v · count(v). Picking bucket v forbids v±1 — exactly House Robber on the points[] array indexed by value.
int deleteAndEarn(int[] nums) {
int max = 0;
for (int x : nums) max = Math.max(max, x);
int[] points = new int[max + 1];
for (int x : nums) points[x] += x;
int prev = 0, curr = 0;
for (int v = 0; v <= max; v++) {
int t = Math.max(curr, prev + points[v]);
prev = curr; curr = t;
}
return curr;
}Complexity — Time O(n + max); Space O(max). Say aloud in an interview: "spot the reduction — every 'pick or skip with adjacency taboo' is House Robber wearing a different hat."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute subsets | O(2ⁿ · n) | O(n) | Reference; TLE past n=20 |
| Reduce to House Robber | O(n + max) | O(max) | Canonical |
When to use which
- "Adjacent-value taboo" → reduce to House Robber.
- Sparse values → skip zeros; use TreeMap.