Code Implementation

class Solution:
    def deleteAndEarn(self, nums):
        from collections import Counter
        if not nums:
            return 0
        count = Counter(nums)
        max_num = max(nums)
        earn = [0] * (max_num + 1)
        for num in range(len(earn)):
            earn[num] = count.get(num, 0) * num

        take, skip = 0, 0
        for i in range(len(earn)):
            take_i = skip + earn[i]
            skip_i = max(skip, take)
            take, skip = take_i, skip_i
        return max(take, skip)
      

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> sum(maxNum + 1, 0);
        for (int n : nums) {
            sum[n] += n;
        }
        int take = 0, skip = 0;
        for (int i = 0; i <= maxNum; ++i) {
            int take_i = skip + sum[i];
            int skip_i = max(skip, take);
            take = take_i;
            skip = skip_i;
        }
        return max(take, skip);
    }
};
      

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 0) return 0;
        int maxNum = 0;
        for (int n : nums) maxNum = Math.max(maxNum, n);
        int[] sum = new int[maxNum + 1];
        for (int n : nums) sum[n] += n;
        int take = 0, skip = 0;
        for (int i = 0; i <= maxNum; i++) {
            int take_i = skip + sum[i];
            int skip_i = Math.max(skip, take);
            take = take_i;
            skip = skip_i;
        }
        return Math.max(take, skip);
    }
}
      

var deleteAndEarn = function(nums) {
    if (nums.length === 0) return 0;
    let maxNum = Math.max(...nums);
    let sum = new Array(maxNum + 1).fill(0);
    for (let n of nums) sum[n] += n;
    let take = 0, skip = 0;
    for (let i = 0; i <= maxNum; ++i) {
        let take_i = skip + sum[i];
        let skip_i = Math.max(skip, take);
        take = take_i;
        skip = skip_i;
    }
    return Math.max(take, skip);
};
      

Problem Description

Given an array of integers called nums, you can perform the following operation any number of times: pick any number x from nums and earn x points. However, after picking x, all instances of x-1 and x+1 are also deleted from the array and cannot be used again.

Your task is to maximize the total points you can earn by repeating this operation optimally until the array is empty.

• Each element in nums can be used at most once (when picked).
• There may be multiple instances of the same number in nums.
• You must not reuse deleted elements.
• Return the maximum points that can be earned.

Thought Process

At first glance, this problem looks like a greedy selection problem: always pick the largest number to maximize points. However, because picking a number removes its neighbors (x-1 and x+1), a greedy approach can fail. For example, picking a large number might prevent you from picking several smaller numbers whose total is greater.

This constraint is similar to the classic "House Robber" problem: you cannot pick adjacent houses. Here, the "houses" are numbers, and adjacency is defined by the number's value, not their position in the array.

The brute-force approach (trying all combinations) is too slow. We need a way to efficiently decide, for each possible number, whether to "take" it (and lose its neighbors) or "skip" it (and keep the option to take its neighbors).

Solution Approach

Let's break down the optimized solution step by step:

1. Count the points for each number:
   • For each unique number in nums, calculate its total contribution (number of times it appears multiplied by its value).
   • This gives us an array (or map) where each index corresponds to a number, and the value is the total points you get by picking all instances of that number.
2. Reframe the problem as "House Robber":
   • Now, you can only pick a number if you didn't pick its neighbor. This is exactly like the "House Robber" dynamic programming problem where you can't rob adjacent houses.
3. Set up dynamic programming:
   • Let earn[i] be the total points for number i.
   • Let take be the max points if you take the current number, and skip be the max if you skip it.
   • For each number from 0 to the largest number in nums:
     • If you take i, you must have skipped i-1: take_i = skip + earn[i].
     • If you skip i, take the max of previous take and skip: skip_i = max(skip, take).
   • Iterate this process for all numbers, and at the end, return max(take, skip).

Why use an array? By using an array indexed by number value (from 0 to max in nums), we make lookups and updates O(1) for each possible number.

Example Walkthrough

Let's use the input nums = [3, 4, 2].

1. Count points:
   • 2 appears once: 2 points
   • 3 appears once: 3 points
   • 4 appears once: 4 points
2. Create earn array: earn = [0, 0, 2, 3, 4]
3. Dynamic programming steps:
   • i = 0: take = 0 + 0 = 0, skip = max(0,0) = 0
   • i = 1: take = 0 + 0 = 0, skip = max(0,0) = 0
   • i = 2: take = 0 + 2 = 2, skip = max(0,0) = 0
   • i = 3: take = 0 + 3 = 3, skip = max(2,0) = 2
   • i = 4: take = 2 + 4 = 6, skip = max(3,2) = 3
4. Result: max(take, skip) = max(6, 3) = 6
5. Why? The optimal solution is to pick 2 (2 points), skip 3, and pick 4 (4 points), totaling 6.

Time and Space Complexity

• Brute-force approach:
  • Try all subsets, which is O(2ⁿ) time – infeasible for large arrays.
• Optimized dynamic programming approach:
  • Counting step: O(n), where n is the length of nums.
  • DP step: O(M), where M is the maximum number in nums (since we process each possible number once).
  • Total time: O(n + M).
  • Space: O(M) for the earn array.

This is efficient because even if n is large, M (the max number) is often manageable.

Summary

The "Delete and Earn" problem is solved efficiently by transforming it into a dynamic programming problem similar to "House Robber." By aggregating the points for each number and using a simple DP recurrence (take or skip), we avoid brute-force enumeration and achieve an optimal solution. The key insight is to realize that picking a number removes its neighbors, just like robbing a house prevents robbing adjacent houses. This approach is not only efficient but also elegantly leverages classic DP patterns.