Command Palette

Search for a command to run...

Hectal
Problem 28.5 · DP Foundations: 1DMedium

Delete and Earn

Pattern1D Dynamic ProgrammingFrequency Counting

What it teaches: Transforming a problem into House Robber by bucketing values.

Practise it on judges as “Delete and Earn”.

The problem

Pick nums[i] to earn its value; every element equal to nums[i] − 1 or nums[i] + 1 is then deleted. Return the maximum points.

Example 1

Input: nums = [2,2,3,3,3,4]
Output: 9

Take all three 3s.

Constraints

  • 1 ≤ n ≤ 2 × 10⁴
  • 1 ≤ nums[i] ≤ 10⁴

Pattern clues in the wording

  • → Choosing v forbids v ± 1

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int deleteAndEarn(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [3,4,2]
6
2
nums = [2,2,3,3,3,4]
9

From slow to fast

Approaches

1. Bucket + House Robber · O(n + max)
1

Bucket + House Robber

Time O(n + max) Space O(max)

Sum values into points[v]; run take/skip over v = 0..max.

Approach 1
class Solution {
    public 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 prev2 = 0, prev1 = 0;
        for (int v = 0; v <= max; v++) {
            int cur = Math.max(prev1, prev2 + points[v]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Verdict: A disguise of House Robber.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One distinct value
  • Gaps between values

Mistakes people make

  • Choosing the most frequent value greedily.

Interview

Follow-up questions

What if values go up to 10⁹?