Scale Engineer

Delete and Earn

Med
#0694Time: `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`.3 companies
Patterns
Dynamic Programming
Data structures
ArrayHash Table
Companies
AccentureCitadelAkuna Capital

Prompt

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 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 * 104
  • 1 <= 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 maxNum in nums.
  • Create and populate the points array of size maxNum + 1 where points[i] is the sum of all numbers equal to i.
  • Create a dp array of size maxNum + 1.
  • Initialize the base cases: dp[0] = 0 and dp[1] = points[1].
  • Iterate from i = 2 to maxNum:
    • Calculate dp[i] using the formula: dp[i] = max(dp[i-1], dp[i-2] + points[i]).
  • 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]). Since points[0] is 0, this simplifies to dp[1] = points[1]. We then iterate from i = 2 up to maxNum. 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 number i.
  • dp[i-2] + points[i] represents the case where we take number i. 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.

Solutions

select [ i ] = nonSelect [ i - 1 ] + sums [ i ]; nonSelect [ i ] = Math . max ( select [ i - 1 ], nonSelect [ i - 1 ]);

Video 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.

← Previous

Previous problem

Next →

Next problem