740. Delete and Earn - Solution

Q: Is Delete and Earn easy or hard?

Delete and Earn is rated Medium on LeetCode because the main challenge is recognizing the hidden transformation to the House Robber dynamic programming problem. Once that pattern is identified, the implementation becomes a straightforward linear DP.

Q: How to solve Delete and Earn in O(n)?

Aggregate the total score contributed by each number into a points array where points[i] = i multiplied by its frequency. Then apply the House Robber recurrence: dp[i] = max(dp[i-1], dp[i-2] + points[i]). This avoids sorting and processes the values sequentially.

Q: What is the best approach for Delete and Earn?

The best approach converts the problem into the House Robber dynamic programming pattern. First aggregate total points for each value, then run DP where choosing value i prevents choosing i-1 and i+1. Using a points array allows a linear scan and runs in O(n + maxVal) time with O(maxVal) space.

Q: Is Delete and Earn asked at Google/Amazon/Meta?

Delete and Earn appears frequently in technical interview preparation lists and has been reported in interviews at companies like Amazon and Meta. The problem tests recognition of dynamic programming patterns, particularly transforming problems into the House Robber recurrence.

Q: What data structure is used in Delete and Earn?

Common implementations use either a hash map or an array to aggregate the total points for each value. After aggregation, dynamic programming is applied across the values to decide whether to include or skip each number.

Q: What is the time complexity of Delete and Earn?

The optimal solution runs in O(n + maxVal) time using a points array and dynamic programming. Building the points array takes O(n), and the DP scan across values up to the maximum number takes O(maxVal). A map-based version with sorted keys runs in O(n log n).

Q: Delete and Earn Python or Java solution approach?

Both Python and Java implementations typically follow the same two steps: accumulate points for each value and then apply House Robber style DP. Python often uses a list for the points array, while Java implementations frequently use either arrays or a HashMap followed by sorted traversal.

The problem

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⁴

Approach overview

Problem Overview: You are given an array of integers. Picking a number x earns x points, but forces you to delete every occurrence of x-1 and x+1. The goal is to maximize total points. The key realization: picking values affects neighboring values, which makes this problem structurally identical to the classic House Robber dynamic programming pattern.

Approach 1: Dynamic Programming with Map (O(n log n) time, O(n) space)

Start by aggregating the total points each number can contribute. Use a hash map where the key is the number and the value is the total points earned from all occurrences of that number. After building the map, extract and sort the unique keys. Then run dynamic programming across the sorted values. If two numbers are consecutive (difference of 1), choosing one prevents choosing the other, just like adjacent houses in House Robber. Maintain two states: the best score including the current number and excluding it. Sorting costs O(n log n), while the DP pass is linear. This approach works well when the value range is large but the number of unique elements is relatively small. It relies heavily on hash table lookups and ordered traversal.

Approach 2: Dynamic Programming with Points Array (O(n + maxVal) time, O(maxVal) space)

This version removes sorting entirely by converting the problem into a dense array. First compute the maximum value in the input. Create a points array where points[i] stores the total points earned from value i. Iterate through the input and accumulate points[num] += num. Once built, the array behaves exactly like the House Robber problem: at index i, either take points[i] plus the best result from i-2, or skip it and keep the result from i-1. This produces a simple linear DP transition. The algorithm runs in O(n + maxVal) time with O(maxVal) space. Because it converts the problem into a sequential DP scan, it cleanly demonstrates patterns used in dynamic programming and array-based state transitions.

Recommended for interviews: The points-array dynamic programming approach is typically expected. It clearly shows that you recognized the hidden House Robber pattern and reduced the problem to a one‑dimensional DP recurrence. Mentioning the map-based approach first demonstrates problem exploration, but the array DP solution highlights stronger algorithmic insight and achieves linear performance without sorting.

Approach 1: Dynamic Programming with Points Array

This approach is based on converting the problem into another known dynamic programming problem, similar to the 'House Robber' problem. The idea is to first calculate the total points for each number by multiplying its value by its frequency in the array. This allows us to transform the problem into finding the optimal way to select values in a linear array where selecting one value prevents selecting its direct neighbors.

Python

def deleteAndEarn(nums):
    max_num = max(nums)
    points = [0] * (max_num + 1)
    for num in nums:
        points[num] += num
    
    take, skip = 0, 0
    for point in points:
        take, skip = skip + point, max(take, skip)
    return max(take, skip)

C++

#include <vector>
#include <algorithm>
using namespace std;

int deleteAndEarn(vector<int>& nums) {
    int maxNum = *max_element(nums.begin(), nums.end());
    vector<int> points(maxNum + 1, 0);
    for (int num : nums) {
        points[num] += num;
    }

    int take = 0, skip = 0;
    for (int point : points) {
        int take_i = skip + point;
        int skip_i = max(take, skip);
        take = take_i;
        skip = skip_i;
    }
    return max(take, skip);
}

This Python solution starts by identifying the maximum number in the array to establish the range of a new points array. It increments each position in the points array by the value times its occurrence. We then iterate over this points array, applying a dynamic programming strategy similar to solving 'House Robber', determining for each value whether taking it or skipping it yields more points.

Complexity

Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums.
Space Complexity: O(m) used by the points array.

Try this approach in the editor

Approach 2: Dynamic Programming with Map

This approach uses a map to store the points for each number, avoiding the space usage related to the maximum number in the points array and processing only numbers that exist in the input. We can still utilize a dynamic programming strategy to compute maximum points.

Java

import java.util.Map;
import java.util.HashMap;

public class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> pointsMap = new HashMap<>();
        for (int num : nums) {
            pointsMap.put(num, pointsMap.getOrDefault(num, 0) + num);
        }
        
        int prev2 = 0, prev1 = 0;
        for (int key : pointsMap.keySet()) {
            int curr = pointsMap.get(key) + Math.max(prev2, prev1);
            prev2 = prev1;
            prev1 = curr;
        }
        return Math.max(prev1, prev2);
    }
}

JavaScript

function deleteAndEarn(nums) {
    const pointsMap = new Map();
    nums.forEach(num => {
        pointsMap.set(num, (pointsMap.get(num) || 0) + num);
    });
    const uniqueKeys = Array.from(pointsMap.keys()).sort((a, b) => a - b);
    let prev2 = 0, prev1 = 0;
    for (let i = 0; i < uniqueKeys.length; ++i) {
        const currPoints = pointsMap.get(uniqueKeys[i]) + Math.max(prev2, prev1);
        prev2 = prev1;
        prev1 = currPoints;
    }
    return Math.max(prev1, prev2);
}

In this Java solution, we map each number to its accumulated points. This avoids predefined array size based on max number and allows compact representation for sparse input. We then iterate over the map and use dynamic programming to find the maximum points.

Complexity

Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums.
Space Complexity: O(k) for storing elements in map.

Try this approach in the editor

Approach 3: Default Approach

func deleteAndEarn(nums []int) int {

	max := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}

	mx := math.MinInt32
	for _, num := range nums {
		mx = max(mx, num)
	}
	total := make([]int, mx+1)
	for _, num := range nums {
		total[num] += num
	}
	first := total[0]
	second := max(total[0], total[1])
	for i := 2; i <= mx; i++ {
		cur := max(first+total[i], second)
		first = second
		second = cur
	}
	return second
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Points Array	Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums. Space Complexity: O(m) used by the points array.
Dynamic Programming with Map	Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums. Space Complexity: O(k) for storing elements in map.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Map	O(n log n)	O(n)	When values are sparse or the maximum value is very large compared to array size
Dynamic Programming with Points Array	O(n + maxVal)	O(maxVal)	General case and most interview settings where value range is manageable

Frequently asked questions

Is Delete and Earn easy or hard?

Delete and Earn is rated Medium on LeetCode because the main challenge is recognizing the hidden transformation to the House Robber dynamic programming problem. Once that pattern is identified, the implementation becomes a straightforward linear DP.

How to solve Delete and Earn in O(n)?

Aggregate the total score contributed by each number into a points array where points[i] = i multiplied by its frequency. Then apply the House Robber recurrence: dp[i] = max(dp[i-1], dp[i-2] + points[i]). This avoids sorting and processes the values sequentially.

What is the best approach for Delete and Earn?

The best approach converts the problem into the House Robber dynamic programming pattern. First aggregate total points for each value, then run DP where choosing value i prevents choosing i-1 and i+1. Using a points array allows a linear scan and runs in O(n + maxVal) time with O(maxVal) space.

Is Delete and Earn asked at Google/Amazon/Meta?

Delete and Earn appears frequently in technical interview preparation lists and has been reported in interviews at companies like Amazon and Meta. The problem tests recognition of dynamic programming patterns, particularly transforming problems into the House Robber recurrence.

What data structure is used in Delete and Earn?

Common implementations use either a hash map or an array to aggregate the total points for each value. After aggregation, dynamic programming is applied across the values to decide whether to include or skip each number.

What is the time complexity of Delete and Earn?

The optimal solution runs in O(n + maxVal) time using a points array and dynamic programming. Building the points array takes O(n), and the DP scan across values up to the maximum number takes O(maxVal). A map-based version with sorted keys runs in O(n log n).

Delete and Earn Python or Java solution approach?

Both Python and Java implementations typically follow the same two steps: accumulate points for each value and then apply House Robber style DP. Python often uses a list for the points array, while Java implementations frequently use either arrays or a HashMap followed by sorted traversal.

Delete and Earn solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Points Array

Approach 2: Dynamic Programming with Map

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Delete and Earn solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Points Array

Approach 2: Dynamic Programming with Map

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems