Delete and Earn
MedPrompt
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:
- Pick any
nums[i]and delete it to earnnums[i]points. Afterwards, you must delete every element equal tonums[i] - 1and every element equal tonums[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] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is an iterative version of the top-down DP. Instead of using recursion, we build a DP table from the bottom up. We calculate the maximum points for each number i based on the already computed values for i-1 and i-2. This avoids recursion and is generally more efficient in practice.
Algorithm
- Find the maximum number
maxNuminnums. - Create and populate the
pointsarray of sizemaxNum + 1wherepoints[i]is the sum of all numbers equal toi. - Create a
dparray of sizemaxNum + 1. - Initialize the base cases:
dp[0] = 0anddp[1] = points[1]. - Iterate from
i = 2tomaxNum:- Calculate
dp[i]using the formula:dp[i] = max(dp[i-1], dp[i-2] + points[i]).
- Calculate
- The result is
dp[maxNum].
Walkthrough
The preprocessing step is the same: we create a points array that aggregates the total points for each number. Let maxNum be the maximum value in nums.
We create a DP array, dp, of size maxNum + 1. dp[i] will store the maximum points that can be earned by considering numbers from 0 to i.
We initialize the base cases for the DP table:
dp[0] = points[0](which is 0 since numbers are positive).dp[1] = max(points[0], points[1]). Sincepoints[0]is 0, this simplifies todp[1] = points[1]. We then iterate fromi = 2up tomaxNum. In each iteration, we apply the same recurrence relation as in the top-down approach:dp[i] = max(dp[i-1], dp[i-2] + points[i])dp[i-1]represents the case where we skip numberi.dp[i-2] + points[i]represents the case where we take numberi. After the loop completes,dp[maxNum]will hold the maximum points that can be earned from all the numbers, which is our final answer.
class Solution { public int deleteAndEarn(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxNum = 0; for (int num : nums) { maxNum = Math.max(maxNum, num); } int[] points = new int[maxNum + 1]; for (int num : nums) { points[num] += num; } if (maxNum == 0) return 0; if (maxNum == 1) return points[1]; int[] dp = new int[maxNum + 1]; dp[0] = 0; dp[1] = points[1]; for (int i = 2; i <= maxNum; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + points[i]); } return dp[maxNum]; }}Complexity
Time
`O(N + M)`, where `N` is the length of `nums` and `M` is the maximum value. `O(N)` for building `points` and `O(M)` for the DP loop.
Space
`O(M)`. We need `O(M)` for the `points` array and `O(M)` for the `dp` array, where `M` is the maximum value in `nums`.
Trade-offs
Pros
Avoids recursion, eliminating the risk of stack overflow and reducing function call overhead.
Typically faster than the memoized recursion approach.
The logic is clear and easy to follow.
Cons
Uses
O(M)extra space for the DP table, which can be optimized.
This is the most efficient approach. It builds upon the bottom-up DP but recognizes that to compute dp[i], we only need the results for dp[i-1] and dp[i-2]. Therefore, we can get rid of the dp array and use just two variables to keep track of the previous two maximums, reducing the space complexity for the DP calculation to O(1).
Algorithm
- Find the maximum number
maxNuminnums. - Create and populate the
pointsarray of sizemaxNum + 1. - Initialize two variables:
prev2 = 0andprev = points[1]. - Iterate from
i = 2tomaxNum:- Calculate
current = max(prev, prev2 + points[i]). - Update
prev2 = prev. - Update
prev = current.
- Calculate
- After the loop,
prevcontains the maximum possible points. Returnprev.
Walkthrough
The preprocessing step of creating the points array remains the same.
Instead of a full dp array, we use two integer variables:
prev: to store the maximum points up toi-1(equivalent todp[i-1])prev2: to store the maximum points up toi-2(equivalent todp[i-2]) We initialize these variables based on the base cases:prev2 = 0(representing the max points before considering any number, ordp[-1])prev = points[1](representingdp[1], asdp[0]is 0). We then iterate fromi = 2up tomaxNum. In each iteration:- We calculate the
currentmax points for numberi:current = max(prev, prev2 + points[i]). - We then update our variables for the next iteration:
prev2becomes the oldprev, andprevbecomes thecurrentvalue we just calculated. After the loop,prevwill hold the final answer, which is the maximum points earnable up tomaxNum.
class Solution { public int deleteAndEarn(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxNum = 0; for (int num : nums) { maxNum = Math.max(maxNum, num); } int[] points = new int[maxNum + 1]; for (int num : nums) { points[num] += num; } if (maxNum == 0) return 0; int prev2 = 0; // Corresponds to dp[i-2] int prev = points[1]; // Corresponds to dp[i-1] for (int i = 2; i <= maxNum; i++) { int current = Math.max(prev, prev2 + points[i]); prev2 = prev; prev = current; } return prev; }}Complexity
Time
`O(N + M)`, where `N` is the length of `nums` and `M` is the maximum value. The complexity is identical to the previous DP approaches.
Space
`O(M)`. Although the DP calculation itself is `O(1)`, we still need the `points` array of size `O(M)`, where `M` is the maximum value in `nums`. This is the most space-efficient solution.
Trade-offs
Pros
Most space-efficient solution.
Retains the time efficiency of the standard bottom-up DP approach.
Simple to implement.
Cons
The logic with
prevandprev2might be slightly less intuitive at first glance compared to using a full DP array.
This approach transforms the problem into a variation of the classic "House Robber" problem. We first process the input array to calculate the total points obtainable for each number. Then, we use a recursive function with memoization to decide whether to "rob" (take the points for) each number i or not. If we take i, we cannot take i-1.
Algorithm
- Find the maximum number
maxNumin the input arraynums. - Create an array
pointsof sizemaxNum + 1to store the total points for each number. - Iterate through
numsand populate thepointsarray:points[num] += num. - Create a memoization array
memoof the same size, initialized to an indicator value (e.g., -1). - Implement a recursive function
rob(i)that calculates the maximum points up to numberi. - In
rob(i):- Handle base cases: if
i < 0, return 0. - If
memo[i]is already computed, return it. - Otherwise, compute
max(points[i] + rob(i-2), rob(i-1)), store it inmemo[i], and return it.
- Handle base cases: if
- The final result is the value of
rob(maxNum).
Walkthrough
First, we need to aggregate the points for each number. Since taking a number x means we should take all occurrences of x, the total points for x is x * count(x). We can use an array, let's call it points, to store these aggregated values. The size of this array will be determined by the maximum value in the nums array.
Let maxNum be the maximum value in nums. We create points array of size maxNum + 1. We iterate through nums, and for each num, we update points[num] += num.
Now, the problem is equivalent to: given the points array, find the maximum sum of elements such that no two chosen elements are adjacent. This is the House Robber problem.
We define a recursive function, say maxPoints(i), which computes the maximum points we can earn from numbers up to i.
For each number i, we have two choices:
- Take
i: We earnpoints[i]. Since we takei, we cannot takei-1. The maximum points we could have earned before that ismaxPoints(i-2). So, total points =points[i] + maxPoints(i-2). - Skip
i: We earn 0 points fromi. The maximum points we can earn is whatever we could get from numbers up toi-1, which ismaxPoints(i-1). The recurrence relation ismaxPoints(i) = max(points[i] + maxPoints(i-2), maxPoints(i-1)). To avoid recomputing the same subproblems, we use a memoization table (an arraymemo) to store the results ofmaxPoints(i). The final answer ismaxPoints(maxNum).
import java.util.HashMap;import java.util.Map; class Solution { private int[] memo; private int[] points; public int deleteAndEarn(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxNum = 0; for (int num : nums) { maxNum = Math.max(maxNum, num); } points = new int[maxNum + 1]; for (int num : nums) { points[num] += num; } memo = new int[maxNum + 1]; for (int i = 0; i <= maxNum; i++) { memo[i] = -1; } return rob(maxNum); } private int rob(int i) { if (i < 0) { return 0; } if (i == 0) { return points[0]; } if (memo[i] != -1) { return memo[i]; } int take = points[i] + rob(i - 2); int skip = rob(i - 1); memo[i] = Math.max(take, skip); return memo[i]; }}Complexity
Time
`O(N + M)`, where `N` is the length of `nums` and `M` is the maximum value in `nums`. `O(N)` to build the `points` array and `O(M)` for the recursive calls, as each state `rob(i)` is computed only once.
Space
`O(M)`. We need `O(M)` space for the `points` array, `O(M)` for the `memo` array, and `O(M)` for the recursion stack in the worst case, where `M` is the maximum value in `nums`.
Trade-offs
Pros
Conceptually straightforward, directly translating the recurrence relation into code.
Guaranteed to find the optimal solution.
Cons
Can lead to a
StackOverflowErrorfor very largeMif the recursion depth limit is exceeded (not an issue with the given constraints).Slightly higher overhead compared to the iterative bottom-up approach due to function calls.
Solutions
Solution
select [ i ] = nonSelect [ i - 1 ] + sums [ i ]; nonSelect [ i ] = Math . max ( select [ i - 1 ], nonSelect [ i - 1 ]);class Solution {public: int deleteAndEarn(vector<int> &nums) { vector<int> vals(10010); for (int &num : nums) { vals[num] += num; } return rob(vals); } int rob(vector<int> &nums) { int a = 0, b = nums[0]; for (int i = 1; i < nums.size(); ++i) { int c = max(nums[i] + a, b); a = b; b = c; } return b; }};class Solution: def deleteAndEarn(self, nums: List[int]) -> int: mx = - inf for num in nums: mx = max(mx, num) total = [0] * (mx + 1) for num in nums: total[num] += num first = total[0] second = max(total[0], total[1]) for i in range(2, mx + 1): cur = max(first + total[i], second) first = second second = cur return secondVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.