LeetCode 740: Delete and Earn

Problem Restatement

We are given an integer array nums.

We may repeatedly choose a number x.

When we choose x:

1. We earn x points.
2. Every occurrence of x - 1 is deleted.
3. Every occurrence of x + 1 is deleted.

We can continue until no numbers remain.

We need to return the maximum total points we can earn.

The official problem states that after taking a value x, every occurrence of x - 1 and x + 1 becomes unavailable. (leetcode.com)

Input and Output

Example function shape:

def deleteAndEarn(nums: list[int]) -> int:
    ...

Examples

Example 1

nums = [3, 4, 2]

If we choose 4, then 3 is deleted.

That gives:

4 points

If we choose 2, nothing conflicts with it afterward.

Total:

4 + 2 = 6

The answer is:

6

Example 2

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

The total value for each number is:

If we take 3, then 2 and 4 are removed.

That gives:

9

If we instead take 2 and 4, we get:

4 + 4 = 8

So the best answer is:

9

First Thought: Recursive Choices

At each step, we can choose some value x.

Then values x - 1 and x + 1 become forbidden.

This looks like a recursive decision problem.

But directly simulating deletions is complicated and inefficient.

The important observation is that only the numeric values matter, not their positions in the array.

Key Insight

Group equal numbers together.

Suppose:

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

Instead of thinking about individual elements, think about total gain per value:

2 -> 4
3 -> 9
4 -> 4

Now the problem becomes:

choose values without taking adjacent numbers

This is exactly the same structure as House Robber.

In House Robber:

• Robbing house i forbids house i - 1 and i + 1.

Here:

• Taking value x forbids x - 1 and x + 1.

So we convert the problem into a linear DP over values.

Algorithm

1. Count the total points contributed by each value.
2. Let:

points[x]

store the total score from value x.

3. Process values from 0 to max(nums).

For each value x:

• Either skip it.
• Or take it and add points[x] to the best answer up to x - 2.

Use House Robber DP:

dp[x] = max(
    dp[x - 1],
    dp[x - 2] + points[x]
)

Return the final DP value.

Correctness

For every value x, all occurrences of x should either be taken together or skipped together.

If we take one occurrence of x, then all occurrences of x - 1 and x + 1 become unusable. Taking additional copies of x has no additional restriction, so taking all copies of x is always optimal once we decide to take value x.

Therefore the problem reduces to choosing values on the number line.

For each value x, there are exactly two possibilities:

1. Skip x.

   • Then the best total remains dp[x - 1].

2. Take x.

   • Then x - 1 cannot be taken.
   • The best compatible earlier result is dp[x - 2].
   • The total becomes dp[x - 2] + points[x].

The recurrence:

dp[x] = max(
    dp[x - 1],
    dp[x - 2] + points[x]
)

therefore considers all optimal possibilities.

The DP processes values in increasing order, so all required earlier states are already known.

Thus the final DP value equals the maximum obtainable score.

Complexity

Let:

m = max(nums)

Here n is the length of nums.

Implementation

class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        if not nums:
            return 0

        max_num = max(nums)

        points = [0] * (max_num + 1)

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

        dp = [0] * (max_num + 1)

        dp[0] = points[0]

        if max_num >= 1:
            dp[1] = max(points[0], points[1])

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

        return dp[max_num]

Code Explanation

We first handle the empty case:

if not nums:
    return 0

Then we compute the largest value:

max_num = max(nums)

The points array stores the total gain for each number:

points[num] += num

For example:

nums = [2, 2, 3]

produces:

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

The DP array stores the best answer up to each value:

dp = [0] * (max_num + 1)

The recurrence is:

dp[x] = max(
    dp[x - 1],
    dp[x - 2] + points[x]
)

This means:

• Skip value x.
• Or take value x and combine it with the best non-adjacent result.

Finally:

return dp[max_num]

returns the optimal answer over all values.

Testing

def run_tests():
    s = Solution()

    assert s.deleteAndEarn([3, 4, 2]) == 6
    assert s.deleteAndEarn([2, 2, 3, 3, 3, 4]) == 9
    assert s.deleteAndEarn([1]) == 1
    assert s.deleteAndEarn([1, 1, 1, 2, 4, 5, 5, 5, 6]) == 18
    assert s.deleteAndEarn([8, 10, 4, 9, 1, 3, 5, 9, 4, 10]) == 37
    assert s.deleteAndEarn([]) == 0

    print("all tests passed")

run_tests()