Delete and Earn
Delete and Earn is a medium dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (bucket totals + house robber), runs in O(n + M) time and O(M) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (pick or skip each distinct value) up.
Problem
You are given an integer array nums. You may repeat the following move as often as you like: pick any remaining element nums[i], earn nums[i] points, and remove it. As a side effect, every remaining element equal to nums[i] - 1 or nums[i] + 1 is removed too, without earning anything.
Return the maximum number of points you can collect.
Examples
Example 1
- Input
nums = [2, 3, 5]- Output
8- Why
- Take 3 (which deletes the 2), then take 5. Taking 2 and 5 would only give 7.
Example 2
- Input
nums = [1, 1, 2, 2, 2, 3]- Output
6- Why
- Taking a 2 deletes every 1 and 3; the remaining 2s are then taken one by one for 2 + 2 + 2 = 6, which beats 1 + 1 + 3 = 5.
Example 3
- Input
nums = [7]- Output
7- Why
- Only one number, so take it.
Constraints
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (pick or skip each distinct value) | O(2ᵏ) | O(n) |
| Optimal (bucket totals + house robber) | O(n + M) | O(M) |
1Brute force (pick or skip each distinct value)
O(2ᵏ)k is the number of distinct values; without memoization every value may branch into two recursive calls.O(n)The grouped values take O(k) ≤ O(n) and the recursion is at most k deep.Group equal values: taking value v earns v × count(v) and forbids v - 1 and v + 1. Sort the distinct values and recurse: at each value either skip it, or take it and jump past the next value if that one is exactly v + 1.
- Build the sorted list of distinct values vals and their totals.
- best(i): if i == k return 0.
- skip = best(i + 1); next = i + 1, or i + 2 if vals[i + 1] == vals[i] + 1.
- Return max(skip, total[i] + best(next)). Answer: best(0).
class Solution {
private int[] vals, totals;
public int deleteAndEarn(int[] nums) {
TreeMap<Integer, Integer> sum = new TreeMap<>();
for (int x : nums) sum.merge(x, x, Integer::sum);
int k = sum.size(), idx = 0;
vals = new int[k];
totals = new int[k];
for (Map.Entry<Integer, Integer> e : sum.entrySet()) {
vals[idx] = e.getKey();
totals[idx++] = e.getValue();
}
return best(0);
}
private int best(int i) {
if (i >= vals.length) return 0;
int skip = best(i + 1);
int next = (i + 1 < vals.length && vals[i + 1] == vals[i] + 1) ? i + 2 : i + 1;
int take = totals[i] + best(next);
return Math.max(skip, take);
}
}class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
total = Counter()
for x in nums:
total[x] += x
vals = sorted(total)
k = len(vals)
def best(i: int) -> int:
if i >= k:
return 0
skip = best(i + 1)
nxt = i + 2 if i + 1 < k and vals[i + 1] == vals[i] + 1 else i + 1
take = total[vals[i]] + best(nxt)
return max(skip, take)
return best(0)class Solution {
vector<int> vals, totals;
int best(int i) {
if (i >= (int)vals.size()) return 0;
int skip = best(i + 1);
int next = (i + 1 < (int)vals.size() && vals[i + 1] == vals[i] + 1) ? i + 2 : i + 1;
int take = totals[i] + best(next);
return max(skip, take);
}
public:
int deleteAndEarn(vector<int>& nums) {
map<int, int> sum;
for (int x : nums) sum[x] += x;
vals.clear();
totals.clear();
for (auto& [v, t] : sum) {
vals.push_back(v);
totals.push_back(t);
}
return best(0);
}
};function deleteAndEarn(nums) {
const sum = new Map();
for (const x of nums) sum.set(x, (sum.get(x) || 0) + x);
const vals = [...sum.keys()].sort((a, b) => a - b);
const k = vals.length;
const best = (i) => {
if (i >= k) return 0;
const skip = best(i + 1);
const next = i + 1 < k && vals[i + 1] === vals[i] + 1 ? i + 2 : i + 1;
const take = sum.get(vals[i]) + best(next);
return Math.max(skip, take);
};
return best(0);
}2Optimal (bucket totals + house robber)
O(n + M)One pass to fill the buckets and one pass over the M = max(nums) possible values.O(M)The bucket array has M + 1 entries; the DP itself keeps only two numbers.Put the points into buckets by value: total[v] = v × count(v). Now neighbouring buckets conflict exactly like neighbouring houses, so run the house-robber DP over total[1..max], keeping only the last two results.
- maxVal = max(nums); total = int[maxVal + 1]; for each x: total[x] += x.
- prev2 = 0 (best up to v - 2), prev1 = 0 (best up to v - 1).
- For v from 1 to maxVal: cur = max(prev1, prev2 + total[v]); prev2 = prev1; prev1 = cur.
- Return prev1.
class Solution {
public int deleteAndEarn(int[] nums) {
int maxVal = 0;
for (int x : nums) maxVal = Math.max(maxVal, x);
int[] total = new int[maxVal + 1];
for (int x : nums) total[x] += x;
int prev2 = 0, prev1 = 0;
for (int v = 1; v <= maxVal; v++) {
int cur = Math.max(prev1, prev2 + total[v]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
max_val = max(nums)
total = [0] * (max_val + 1)
for x in nums:
total[x] += x
prev2 = prev1 = 0
for v in range(1, max_val + 1):
prev2, prev1 = prev1, max(prev1, prev2 + total[v])
return prev1class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int maxVal = *max_element(nums.begin(), nums.end());
vector<int> total(maxVal + 1, 0);
for (int x : nums) total[x] += x;
int prev2 = 0, prev1 = 0;
for (int v = 1; v <= maxVal; v++) {
int cur = max(prev1, prev2 + total[v]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};function deleteAndEarn(nums) {
const maxVal = Math.max(...nums);
const total = new Array(maxVal + 1).fill(0);
for (const x of nums) total[x] += x;
let prev2 = 0, prev1 = 0;
for (let v = 1; v <= maxVal; v++) {
const cur = Math.max(prev1, prev2 + total[v]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}Edge cases to test
- A single number
- All numbers equal: take them all
- Values with gaps (like 2 and 5) never conflict with each other
- A long chain of consecutive values, where it behaves like robbing houses in a row
Hints
Hint 1
Once you take one copy of a value v, you may as well take every copy of v: the copies of v itself are never deleted by taking v.
Hint 2
So each distinct value v is worth total[v] = v × (count of v), and you cannot take both v and v + 1.
Hint 3
That is exactly the house-robber problem on the array total[0..max]: dp[v] = max(dp[v - 1], dp[v - 2] + total[v]).
FAQ
What is the best time complexity for Delete and Earn?
Optimal (bucket totals + house robber) runs in O(n + M) time and O(M) extra space. One pass to fill the buckets and one pass over the M = max(nums) possible values.
Which pattern does Delete and Earn use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Delete and Earn?
Yes. Brute force (pick or skip each distinct value) takes O(2ᵏ) time and O(n) space. Group equal values: taking value v earns v × count(v) and forbids v - 1 and v + 1.
Which edge cases should I test for Delete and Earn?
A single number; All numbers equal: take them all; Values with gaps (like 2 and 5) never conflict with each other; A long chain of consecutive values, where it behaves like robbing houses in a row.