Delete and Earn

MEDIUM

Description

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 * 10⁴
1 <= nums[i] <= 10⁴

Approaches

Checkout 3 different approaches to solve Delete and Earn. Click on different approaches to view the approach and algorithm in detail.

Bottom-Up Dynamic Programming

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

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 Analysis

Time Complexity: `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 Complexity: `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`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Delete and Earn. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Delete and Earn

Patterns:

Dynamic Programming

Data Structures:

ArrayHash Table

Companies:

Accenture |Citadel |Akuna Capital |