Delete and Earn

Medium Dynamic Programming 1D DP Original on LeetCode

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^4
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(2ᵏ)k is the number of distinct values; without memoization every value may branch into two recursive calls.
SpaceO(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.

  1. Build the sorted list of distinct values vals and their totals.
  2. best(i): if i == k return 0.
  3. skip = best(i + 1); next = i + 1, or i + 2 if vals[i + 1] == vals[i] + 1.
  4. 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);
    }
}

2Optimal (bucket totals + house robber)

TimeO(n + M)One pass to fill the buckets and one pass over the M = max(nums) possible values.
SpaceO(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.

  1. maxVal = max(nums); total = int[maxVal + 1]; for each x: total[x] += x.
  2. prev2 = 0 (best up to v - 2), prev1 = 0 (best up to v - 1).
  3. For v from 1 to maxVal: cur = max(prev1, prev2 + total[v]); prev2 = prev1; prev1 = cur.
  4. 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;
    }
}

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.