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.
This approach is based on converting the problem into another known dynamic programming problem, similar to the 'House Robber' problem. The idea is to first calculate the total points for each number by multiplying its value by its frequency in the array. This allows us to transform the problem into finding the optimal way to select values in a linear array where selecting one value prevents selecting its direct neighbors.
This Python solution starts by identifying the maximum number in the array to establish the range of a new points array. It increments each position in the points array by the value times its occurrence. We then iterate over this points array, applying a dynamic programming strategy similar to solving 'House Robber', determining for each value whether taking it or skipping it yields more points.
Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums.
Space Complexity: O(m) used by the points array.
This approach uses a map to store the points for each number, avoiding the space usage related to the maximum number in the points array and processing only numbers that exist in the input. We can still utilize a dynamic programming strategy to compute maximum points.
In this Java solution, we map each number to its accumulated points. This avoids predefined array size based on max number and allows compact representation for sparse input. We then iterate over the map and use dynamic programming to find the maximum points.
Java
JavaScript
Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums.
Space Complexity: O(k) for storing elements in map.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Points Array | Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums. |
| Dynamic Programming with Map | Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums. |
| Default Approach | — |
| 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 |
Delete and Earn - Dynamic Programming - Leetcode 740 - Python • NeetCode • 63,558 views views
Watch 9 more video solutions →Practice Delete and Earn with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor