Delete and Earn

Medium
308.

Delete and Earn

Delete and Earn is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Adobe and Morgan Stanley interviews.

You are given an integer array nums. You want to maximise the points you earn by repeatedly doing this:

  • Pick any nums[i] and earn nums[i] points. You must then 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.

Example 1

Input
nums = [3,4,2]
Output
6
Explanation
Take 4 (earning 4), which deletes the 3; then take 2.

Example 2

Input
nums = [2,2,3,3,3,4]
Output
9
Explanation
Take the three 3s for 9; the 2s and the 4 are deleted.

Example 3

Input
nums = [1]
Output
1

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete and Earn — Solution in Python, Java & C++

Delete and Earn solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and hash table.

Delete and Earn is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Adobe and Morgan Stanley interviews.

Problem statement

You are given an integer array nums. You want to maximise the points you earn by repeatedly doing this:

  • Pick any nums[i] and earn nums[i] points. You must then 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.

Example 1

Input: nums = [3,4,2]
Output: 6
Explanation: Take 4 (earning 4), which deletes the 3; then take 2.

Example 2

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: Take the three 3s for 9; the 2s and the 4 are deleted.

Example 3

Input: nums = [1]
Output: 1

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 100

Hints for Delete and Earn

  1. Hint 1

    Taking one copy of a value means taking all copies — they never conflict with each other.

  2. Hint 2

    So collapse the array into points[v] = v × count(v), indexed by value.

  3. Hint 3

    Now adjacent values conflict, and the problem is exactly House Robber over that points array.

How to solve Delete and Earn

Taking a value means taking every copy of it, so collapse the array into points[v] = v · count(v). Adjacent values conflict, and the problem is House Robber over that array.

Approach

  1. Build points indexed by value.
  2. Walk values from 1 to max: take = skip + points[v], skip = max(skip, take_prev).
  3. Return max(take, skip).

Why it works

Copies of the same value never delete each other, so choosing a value is all-or-nothing. Choosing v forbids v ± 1 and nothing else, which is exactly the no-two-adjacent constraint the rolling take/skip pair solves optimally.

Complexity

  • Time — O(n + max)
  • Space — O(max)

Pitfalls

  • A sorted map of distinct values handles sparse large values; the dense array is simplest when the range is small.

Reference solution

Python

def deleteAndEarn(nums) -> int:
    max_v = max(nums)
    points = [0] * (max_v + 1)
    for x in nums:
        points[x] += x
    take = skip = 0
    for v in range(1, max_v + 1):
        take, skip = skip + points[v], max(skip, take)
    return max(take, skip)

Java

public static int deleteAndEarn(int[] nums) {
    int maxV = 0;
    for (int x : nums) maxV = Math.max(maxV, x);
    int[] points = new int[maxV + 1];
    for (int x : nums) points[x] += x;
    int take = 0, skip = 0;
    for (int v = 1; v <= maxV; v++) {
        int newTake = skip + points[v];
        int newSkip = Math.max(skip, take);
        take = newTake;
        skip = newSkip;
    }
    return Math.max(take, skip);
}

C++

int deleteAndEarn(vector<int>& nums) {
    int maxV = 0;
    for (int x : nums) maxV = max(maxV, x);
    vector<int> points(maxV + 1, 0);
    for (int x : nums) points[x] += x;
    int take = 0, skip = 0;
    for (int v = 1; v <= maxV; v++) {
        int newTake = skip + points[v];
        int newSkip = max(skip, take);
        take = newTake;
        skip = newSkip;
    }
    return max(take, skip);
}

JavaScript

var deleteAndEarn = function(nums) {
    let maxV = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > maxV) maxV = nums[i];
    }
    const points = new Array(maxV + 1).fill(0);
    for (let i = 0; i < nums.length; i++) points[nums[i]] += nums[i];
    let take = 0, skip = 0;
    for (let v = 1; v <= maxV; v++) {
        const newTake = skip + points[v];
        const newSkip = Math.max(skip, take);
        take = newTake;
        skip = newSkip;
    }
    return Math.max(take, skip);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets