LeetCode 740 - Delete and Earn

LeetCode Problem 740

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming

Solution

Problem Understanding

The problem gives us an integer array nums, and we want to maximize the total number of points earned by repeatedly deleting elements.

When we delete a number x, we gain x points. However, deleting x also forces the removal of every occurrence of x - 1 and x + 1. This restriction is the core challenge of the problem because choosing one value prevents us from choosing its neighboring values.

The important detail is that deleting a single occurrence of a number does not just affect one neighboring element. It removes all instances of adjacent values globally. Because of this, the order of deletions is less important than deciding which values we ultimately keep.

For example, if the array contains several 3s, then taking 3 multiple times may be better than taking 2s and 4s combined. The problem becomes a tradeoff between neighboring values.

The input consists of:

• An integer array nums
• Each value is between 1 and 10^4
• The array length can be as large as 2 * 10^4

The output is a single integer representing the maximum number of points obtainable.

The constraints are important because they rule out exponential solutions. A brute-force search over all deletion combinations would become infeasible very quickly. Since the value range is limited to 10^4, this suggests that grouping numbers by value may be useful.

Several edge cases are important:

• Arrays containing only one distinct value
• Arrays where all values are consecutive
• Arrays with large gaps between values
• Arrays with many duplicates
• Very small arrays, such as length 1

A naive implementation might repeatedly modify arrays or recursively try every possible deletion sequence, which would be extremely slow.

Approaches

Brute Force Approach

A brute-force solution would try every possible deletion order.

At each step, we could pick any remaining number, gain its value, remove all instances of neighboring values, and recursively compute the best possible future score. We would then take the maximum across all choices.

This approach is correct because it explores every valid sequence of operations. Eventually, it finds the optimal one.

However, it is far too slow. The number of possible states grows exponentially because each distinct value creates branching choices. Even with memoization, tracking all possible remaining sets becomes expensive.

The constraints make this approach impractical.

Key Insight

The key observation is that the exact positions of numbers do not matter. Only the total contribution of each value matters.

Suppose the array contains:

• three 2s
• four 3s
• two 4s

Then:

• taking all 2s earns 6
• taking all 3s earns 12
• taking all 4s earns 8

If we choose value 3, we cannot choose 2 or 4.

This transforms the problem into a classic dynamic programming pattern identical to the House Robber problem.

We create an array where:

• points[x] = x * frequency(x)

Now the decision becomes:

• take value x, then skip x - 1
• skip value x

This is exactly the same as deciding whether to rob adjacent houses.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries every deletion combination recursively
Optimal	O(n + k)	O(k)	Dynamic programming over value frequencies

Here:

• n is the length of nums
• k is the maximum value in nums

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Count how many times each number appears.

We first compute the frequency of every value in nums. This allows us to determine the total points obtainable from each distinct number.

For example:

nums = [2,2,3,3,3,4]

frequency:
2 -> 2
3 -> 3
4 -> 1

2. Build a points array.

For every value x, compute:

points[x] = x * frequency[x]

In the example above:

points[2] = 4
points[3] = 9
points[4] = 4

This converts the problem from individual elements into grouped values. 3. Apply dynamic programming.

Define:

dp[i] = maximum points obtainable using values from 0 to i

At each value i, we have two choices:

• Skip i
• Take i, which means we cannot take i - 1

Therefore:

$dp[i]=\max(dp[i-1],\ dp[i-2]+points[i])$ 4. Initialize base cases.

We need starting values for the recurrence.

dp[0] = 0
dp[1] = points[1]

5. Iterate through all possible values.

Since values are bounded by 10^4, we iterate from 2 up to the maximum number in nums.

For each value:

• dp[i - 1] means we skip i
• dp[i - 2] + points[i] means we take i

6. Return the final answer.

The result is stored in:

dp[max_value]

Why it works

The algorithm works because every value only conflicts with its immediate neighbors.

Once the array is transformed into total points per value, the problem becomes equivalent to selecting non-adjacent numbers for maximum sum. The dynamic programming recurrence guarantees that at every step we consider both valid possibilities:

• excluding the current value
• including the current value while excluding its neighbor

Since the recurrence always keeps the best achievable score up to each value, the final answer is optimal.

Python Solution

from typing import List

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        max_value = max(nums)

        points = [0] * (max_value + 1)

        for num in nums:
            points[num] += num

        if max_value == 1:
            return points[1]

        dp = [0] * (max_value + 1)

        dp[0] = 0
        dp[1] = points[1]

        for value in range(2, max_value + 1):
            dp[value] = max(
                dp[value - 1],
                dp[value - 2] + points[value]
            )

        return dp[max_value]

The implementation begins by finding the maximum value in the input array. This determines the size of the points and dp arrays.

The points array stores the total score obtainable from each number. Instead of tracking frequency separately, we directly accumulate the value itself:

points[num] += num

For example, if 3 appears three times, then:

points[3] = 9

This simplifies the later dynamic programming logic.

The special case for max_value == 1 prevents out-of-bounds issues and correctly handles arrays containing only 1s.

The dp array stores the best possible score up to each value. The recurrence compares:

• skipping the current value
• taking the current value plus the best score from two positions earlier

Finally, the algorithm returns the best score for the largest value.

Go Solution

func deleteAndEarn(nums []int) int {
    maxValue := 0

    for _, num := range nums {
        if num > maxValue {
            maxValue = num
        }
    }

    points := make([]int, maxValue+1)

    for _, num := range nums {
        points[num] += num
    }

    if maxValue == 1 {
        return points[1]
    }

    dp := make([]int, maxValue+1)

    dp[0] = 0
    dp[1] = points[1]

    for value := 2; value <= maxValue; value++ {
        take := dp[value-2] + points[value]
        skip := dp[value-1]

        if take > skip {
            dp[value] = take
        } else {
            dp[value] = skip
        }
    }

    return dp[maxValue]
}

The Go implementation follows the same logic as the Python version.

Since Go does not provide a built-in max function for integers, we manually compare values using an if statement.

Slices are used for both the points and dp arrays. Go initializes slices with zero values automatically, which matches the desired behavior.

Integer overflow is not an issue because the maximum possible score is well within Go's integer range.

Worked Examples

Example 1

nums = [3,4,2]

Step 1: Build points array

Value	Total Points
2	2
3	3
4	4

Step 2: Initialize DP

i	dp[i]
0	0
1	0

Step 3: Fill DP

Value	Take	Skip	dp[value]
2	0 + 2 = 2	0	2
3	0 + 3 = 3	2	3
4	2 + 4 = 6	3	6

Final answer:

6

Example 2

nums = [2,2,3,3,3,4]

Step 1: Build points array

Value	Total Points
2	4
3	9
4	4

Step 2: Initialize DP

i	dp[i]
0	0
1	0

Step 3: Fill DP

Value	Take	Skip	dp[value]
2	0 + 4 = 4	0	4
3	0 + 9 = 9	4	9
4	4 + 4 = 8	9	9

Final answer:

9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + k)	Build frequency totals in O(n), then iterate through values up to max number
Space	O(k)	Arrays for points and DP depend on maximum value

Here:

• n is the number of elements in nums
• k is the maximum value in nums

The algorithm is efficient because the value range is bounded. Instead of exploring deletion sequences directly, we aggregate equal values and solve a one-dimensional dynamic programming problem.

Test Cases

solution = Solution()

assert solution.deleteAndEarn([3, 4, 2]) == 6
# Basic example from the problem statement

assert solution.deleteAndEarn([2, 2, 3, 3, 3, 4]) == 9
# Multiple duplicates with adjacent conflicts

assert solution.deleteAndEarn([1]) == 1
# Single element array

assert solution.deleteAndEarn([1, 1, 1, 1]) == 4
# All identical values

assert solution.deleteAndEarn([1, 2, 3, 4, 5]) == 9
# Consecutive values

assert solution.deleteAndEarn([8, 10, 4, 9, 1, 3, 5, 9, 4, 10]) == 37
# Mixed values with multiple optimal choices

assert solution.deleteAndEarn([2, 2, 2, 2]) == 8
# Only one distinct number

assert solution.deleteAndEarn([1, 3, 5, 7]) == 16
# No adjacent conflicts at all

assert solution.deleteAndEarn([10000]) == 10000
# Maximum value boundary

assert solution.deleteAndEarn([9999, 10000]) == 10000
# Adjacent high values

Test	Why
[3,4,2]	Validates the basic example
[2,2,3,3,3,4]	Tests duplicate aggregation
[1]	Smallest possible input
[1,1,1,1]	All identical values
[1,2,3,4,5]	Fully consecutive values
[8,10,4,9,1,3,5,9,4,10]	Complex decision structure
[2,2,2,2]	Single distinct value
[1,3,5,7]	No adjacency conflicts
[10000]	Maximum value constraint
[9999,10000]	Adjacent large numbers

Edge Cases

One important edge case is when the array contains only a single distinct value, such as [2,2,2,2]. A buggy implementation might still attempt to apply adjacency logic unnecessarily. In this case, the correct strategy is simply to take every occurrence. The implementation handles this naturally because the dynamic programming recurrence treats missing neighboring values as zero.

Another important edge case is when every number is consecutive, such as [1,2,3,4,5]. This creates the maximum number of conflicts because choosing any value blocks its neighbors. A greedy strategy could fail here by choosing locally large values instead of globally optimal combinations. The dynamic programming solution correctly evaluates both taking and skipping each value.

A third edge case occurs when there are large gaps between values, such as [1,3,5,7]. Since none of these values are adjacent, all of them can be taken together. Some implementations incorrectly assume every step involves a conflict. The DP formulation handles this correctly because values with zero points simply carry forward previous results.

Another subtle edge case is arrays containing only 1s. Since the recurrence references dp[i - 2], implementations without careful initialization may encounter index errors. The explicit handling of max_value == 1 ensures correctness for this scenario.