Delete and Earn

medium array hash map dp

Problem

Given an integer array nums, pick any element x to earn nums[x] points; doing so deletes every occurrence of x − 1 and x + 1 from the array. Return the maximum total points you can earn.

Inputnums = [2, 2, 3, 3, 3, 4]

Output9

Bucket sums: …, b[2]=4, b[3]=9, b[4]=4. Picking only 3 (deletes 2s and 4s) earns 9.

nums (comma-separated)

def delete_and_earn(nums):
    if not nums:
        return 0
    mx = max(nums)
    bucket = [0] * (mx + 1)
    for x in nums:
        bucket[x] += x
    take = skip = 0
    for v in bucket:
        take, skip = skip + v, max(skip, take)
    return max(take, skip)

function deleteAndEarn(nums) {
  if (nums.length === 0) return 0;
  const mx = Math.max(...nums);
  const bucket = new Array(mx + 1).fill(0);
  for (const x of nums) bucket[x] += x;
  let take = 0, skip = 0;
  for (const v of bucket) {
    [take, skip] = [skip + v, Math.max(skip, take)];
  }
  return Math.max(take, skip);
}

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 0) return 0;
        int mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        int[] bucket = new int[mx + 1];
        for (int x : nums) bucket[x] += x;
        int take = 0, skip = 0;
        for (int v : bucket) {
            int newTake = skip + v;
            int newSkip = Math.max(skip, take);
            take = newTake; skip = newSkip;
        }
        return Math.max(take, skip);
    }
}

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> bucket(mx + 1, 0);
        for (int x : nums) bucket[x] += x;
        int take = 0, skip = 0;
        for (int v : bucket) {
            int newTake = skip + v;
            int newSkip = max(skip, take);
            take = newTake; skip = newSkip;
        }
        return max(take, skip);
    }
};

Explanation

The clever observation is that taking a number x deletes all x-1 and x+1, but never affects other copies of x. So if you take value x at all, you may as well take every copy of it and earn x · count(x) points at once.

That turns the problem into the classic House Robber. First we build a bucket array where bucket[x] is the total points from all copies of x. Now choosing x forbids the adjacent values x-1 and x+1 — exactly like robbing houses where you cannot rob two neighbors.

We sweep the buckets keeping two running values: take (best if we use the current bucket) and skip (best if we don't). Each step updates take = skip + v and skip = max(skip, take), so neighbors are never both used.

Example: nums = [2,2,3,3,3,4]. Buckets become b[2]=4, b[3]=9, b[4]=4. Taking only the 3 bucket earns 9 and forbids the neighboring 2s and 4s, which beats taking 2 and 4 together (8). The answer is 9.

Building the buckets is linear and the House Robber sweep is linear over the value range, so it is fast.

Time: O(n + M) Space: O(M)