Delete and Earn
Medium · Dynamic Programming · Array · Hash Table · Dynamic Programming
Problem
You are given an integer array nums. As often as you like, you may pick any remaining element x, earn x points, and delete it. Picking x also deletes every remaining element equal to x - 1 or x + 1, and those earn nothing.
Return the most points you can collect.
Examples
Input: nums = [1,1,2,5,5,6] Output: 12
Take both 1s (2 points, which deletes the 2) and both 5s (10 points, which deletes the 6): 12.
Input: nums = [4,5,6,6] Output: 16
Taking the 4 and both 6s deletes only the 5: 4 + 12 = 16.
Input: nums = [2,2,2,3] Output: 6
The three 2s earn 6, more than the single 3.
Constraints
- 1 <= len(nums) <= 2 · 10^4
- 1 <= nums[i] <= 10^4
Approaches
- Baseline: sorted values, best compatible earlier value — time O(n + k²), space O(k)
Follow-up
If the values were up to 10^9, an array indexed by value would be too big. Sort the distinct values instead and run the same recurrence over them: neighbors in the sorted list conflict only when they differ by exactly 1.
Related problems
Start free on Cariara · Coding problems · System design studio
