{x}
blog image

Delete and Earn

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

Solution Explanation for Delete and Earn

This problem can be efficiently solved using dynamic programming. The core idea is to recognize that we can't select adjacent numbers. If we pick a number x, we can't pick x-1 or x+1. This resembles the classic "House Robber" problem.

Approach:

  1. Frequency Count: First, we create a frequency array (total) to store the sum of all occurrences of each number in the input nums. This array will contain the points we can earn for selecting each number. For example, if nums is [2,2,3,3,3,4], total will be [0, 0, 4, 9, 4, 0, ...] (because two 2's give 4, three 3's give 9, and one 4 gives 4).

  2. Dynamic Programming: We use dynamic programming to iteratively find the maximum points we can earn. We maintain two variables:

    • first: Represents the maximum points earned considering numbers up to the previous step, excluding the current number.
    • second: Represents the maximum points earned considering numbers up to the previous step, including the current number.

  3. Iteration: We iterate through the total array, starting from index 2 (as index 0 and 1 are base cases). In each iteration:

    • We calculate cur, the maximum points earned up to the current number. It is either the sum of the current number's points (total[i]) plus the maximum points from the previous step without the current number (first), or the maximum points from the previous step including the current number (second).
    • We update first and second to prepare for the next iteration.

  4. Result: After iterating through the entire array, second holds the maximum points achievable, which we return.

Time Complexity: O(N), where N is the maximum value in nums. This is because we iterate through the total array, whose size is determined by the maximum number in nums. The space complexity of creating total is also O(N). If we only consider the input size of nums the time complexity is technically O(max(nums)), which could be bigger than the size of nums.

Space Complexity: O(N), dominated by the total array.

Code Examples (with detailed comments):

Python:

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        mx = max(nums)  # Find the maximum value in nums
        total = [0] * (mx + 1)  # Create frequency array to store points for each number
        for num in nums:
            total[num] += num  # Calculate points for each number (sum of occurrences * number)
 
        first = total[0]  # Base case: Maximum points for first number (0)
        second = max(total[0], total[1])  # Base case: Maximum points for first two numbers
 
        for i in range(2, mx + 1):  # Iterate starting from the third number
            cur = max(first + total[i], second)  # Calculate maximum points including current number
            first = second  # Update first to prepare for the next iteration
            second = cur  # Update second to prepare for the next iteration
 
        return second  # Return the maximum points achievable

Java:

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int num : nums) maxVal = Math.max(maxVal, num);
        int[] points = new int[maxVal + 1];
        for (int num : nums) points[num] += num;
 
        int first = points[0], second = Math.max(points[0], points[1]);
        for (int i = 2; i <= maxVal; i++) {
            int cur = Math.max(first + points[i], second);
            first = second;
            second = cur;
        }
        return second;
    }
}

C++:

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxVal = 0;
        for (int num : nums) maxVal = max(maxVal, num);
        vector<int> points(maxVal + 1, 0);
        for (int num : nums) points[num] += num;
 
        int first = points[0], second = max(points[0], points[1]);
        for (int i = 2; i <= maxVal; i++) {
            int cur = max(first + points[i], second);
            first = second;
            second = cur;
        }
        return second;
    }
};

Go:

func deleteAndEarn(nums []int) int {
	maxVal := 0
	for _, num := range nums {
		maxVal = max(maxVal, num)
	}
	points := make([]int, maxVal+1)
	for _, num := range nums {
		points[num] += num
	}
 
	first, second := points[0], max(points[0], points[1])
	for i := 2; i <= maxVal; i++ {
		cur := max(first+points[i], second)
		first = second
		second = cur
	}
	return second
}
 
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

These solutions all follow the same dynamic programming approach with slight variations in syntax. Remember to choose the language most comfortable for you.