Delete and Earn
Problem
Given an array of integers nums, return the maximum points you can earn by deleting elements such that deleting a number also deletes all instances of numbers equal to that number minus one and plus one.
- 1 ≤ nums.length ≤ 2 * 10⁴
- 1 ≤ nums[i] ≤ 10⁴
Example
nums = [3, 4, 2]6Choosing 4 earns 4 points and deletes 3 and 5 (if present). The array becomes [2]. Then choosing 2 earns 2 points. Total points = 6. The algorithm first counts the total points for each unique number: 2 -> 2, 3 -> 3, 4 -> 4. It then uses a DP approach similar to the House Robber problem to decide whether to take or skip each number in ascending order. The critical moment is deciding between taking 4 (and skipping 3) or taking 3 and 2. The DP chooses the optimal combination to maximize points.
Approach
Straightforward Solution
A brute-force approach tries all subsets of numbers, deleting neighbors each time, which is exponential and infeasible for large inputs.
Core Observation
The problem reduces to selecting numbers to maximize points where choosing a number excludes its immediate neighbors (number - 1 and number + 1). This is analogous to the House Robber problem where adjacent houses cannot be robbed together.
Path to Optimal
PreviewBy aggregating points for each unique number (multiplying the number by its frequency), the problem transforms into a linear sequence where each position corresponds to a number and its total points. The adjacency constraint translates to not choosing adjacent indices…
Full step-by-step walkthrough on Pro →
Optimal Approach
Count total points for each number using a frequency map, then iterate from 1 to max number, using DP to decide whether to take or skip each number to maximize total points. This yields an O(n + m) time solution, where n is input size and m is max number value.
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n + m)
Counting frequencies takes O(n). The DP iterates through all numbers up to max_val (m), performing constant work per number, resulting in O(n + m) total time.
Space
O(m)
Auxiliary space is used for the frequency map and DP arrays, each sized by max_val + 1, which is O(m). This space is necessary to store aggregated points and DP states.
Pattern Spotlight
Dynamic Programming (House Robber Variant)
When a problem requires maximizing sum with a constraint that choosing an element excludes its immediate neighbors, transform the problem into a linear DP where each state represents the best solution up to that element, choosing between skipping or taking it.
Solution
| 1 | class Solution: |
| 2 | def deleteAndEarn(self, nums): |
| 3 | freq = Counter(nums) |
| 4 | max_val = max(nums) |
| 5 | |
| 6 | points = [0] * (max_val + 1) |
| 7 | for v, c in freq.items(): |
| 8 | points[v] = v * c |
| 9 | |
| 10 | dp = [0] * (max_val + 1) |
| 11 | dp[1] = points[1] |
| 12 | |
| 13 | for i in range(2, max_val + 1): |
| 14 | dp[i] = max(dp[i-1], dp[i-2] + points[i]) |
| 15 | |
| 16 | return dp[max_val] |
Step-by-Step Solution
Aggregate Total Points for Each Unique Number Using Frequency Counting
| 3 | freq = Counter(nums) |
| 4 | max_val = max(nums) |
| 6 | points = [0] * (max_val + 1) |
| 7 | for v, c in freq.items(): |
| 8 | points[v] = v * c |
Objective
To compute the total points obtainable from each unique number by multiplying the number by its frequency in the input array.
Key Insight
By counting how many times each number appears, the problem simplifies from dealing with individual elements to dealing with total points per number. This aggregation converts the problem into a linear sequence where each index corresponds to a number and its total points, enabling the DP approach.
Interview Quick-Check
Core Logic
Frequency counting aggregates the total points per number, transforming the problem into a linear DP over these aggregated values.
Common Pitfalls & Bugs
Forgetting to multiply the number by its frequency leads to incorrect total points and suboptimal DP results.
Apply Dynamic Programming to Maximize Points with Adjacency Constraints
To use a DP array where each element represents the maximum points achievable up to that number, deciding whether to take or skip it based on adjacency rules.
Return the Maximum Points Achievable After Processing All Numbers
To output the final computed maximum points from the DP array corresponding to the largest number in the input.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
dp[i] = max(dp[i-1], dp[i-2] + points[i])Compute the optimal score for value i using the DP recurrence.
This recurrence encodes the fundamental decision of the problem. Taking value i yields points[i] but prevents selecting i−1, so the best compatible previous result is dp[i−2]. Skipping value i preserves dp[i−1]. Choosing the maximum of these options guarantees that adjacent values are never selected simultaneously while maximizing total reward.
freq = Counter(nums)Count how many times each number appears in nums.
The original array must be reorganized by value rather than position because the deletion rule depends on numerical adjacency (x removes x−1 and x+1). Aggregating frequencies converts scattered duplicates into a single total reward per value, which is necessary to reduce the problem into a one-dimensional dynamic programming structure.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why does aggregating points by number and applying a House Robber style DP solve the problem optimally?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Delete and Earn from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Delete and Earn drill