Watch 10 video solutions for Delete and Earn, a medium level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by NeetCode has 63,558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1:
Input: nums = [3,4,2] Output: 6 Explanation: You can perform the following operations: - Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2]. - Delete 2 to earn 2 points. nums = []. You earn a total of 6 points.
Example 2:
Input: nums = [2,2,3,3,3,4] Output: 9 Explanation: You can perform the following operations: - Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3]. - Delete a 3 again to earn 3 points. nums = [3]. - Delete a 3 once more to earn 3 points. nums = []. You earn a total of 9 points.
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104Problem Overview: You are given an array of integers. Picking a number x earns x points, but forces you to delete every occurrence of x-1 and x+1. The goal is to maximize total points. The key realization: picking values affects neighboring values, which makes this problem structurally identical to the classic House Robber dynamic programming pattern.
Approach 1: Dynamic Programming with Map (O(n log n) time, O(n) space)
Start by aggregating the total points each number can contribute. Use a hash map where the key is the number and the value is the total points earned from all occurrences of that number. After building the map, extract and sort the unique keys. Then run dynamic programming across the sorted values. If two numbers are consecutive (difference of 1), choosing one prevents choosing the other, just like adjacent houses in House Robber. Maintain two states: the best score including the current number and excluding it. Sorting costs O(n log n), while the DP pass is linear. This approach works well when the value range is large but the number of unique elements is relatively small. It relies heavily on hash table lookups and ordered traversal.
Approach 2: Dynamic Programming with Points Array (O(n + maxVal) time, O(maxVal) space)
This version removes sorting entirely by converting the problem into a dense array. First compute the maximum value in the input. Create a points array where points[i] stores the total points earned from value i. Iterate through the input and accumulate points[num] += num. Once built, the array behaves exactly like the House Robber problem: at index i, either take points[i] plus the best result from i-2, or skip it and keep the result from i-1. This produces a simple linear DP transition. The algorithm runs in O(n + maxVal) time with O(maxVal) space. Because it converts the problem into a sequential DP scan, it cleanly demonstrates patterns used in dynamic programming and array-based state transitions.
Recommended for interviews: The points-array dynamic programming approach is typically expected. It clearly shows that you recognized the hidden House Robber pattern and reduced the problem to a one‑dimensional DP recurrence. Mentioning the map-based approach first demonstrates problem exploration, but the array DP solution highlights stronger algorithmic insight and achieves linear performance without sorting.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Map | O(n log n) | O(n) | When values are sparse or the maximum value is very large compared to array size |
| Dynamic Programming with Points Array | O(n + maxVal) | O(maxVal) | General case and most interview settings where value range is manageable |