#740

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Delete and Earn

Maximize points by deleting numbers from an array while removing all adjacent values, using dynamic programming efficiently.

array hash table dynamic programming

Problem Statement

You are given an integer array nums. Each time you pick a number x, you earn x points and must remove all occurrences of x-1 and x+1 from the array. Determine the sequence of picks that maximizes your total points.

Return the maximum points achievable by repeatedly selecting numbers under this deletion constraint. For example, given nums = [3,4,2], deleting 4 first removes 3, then deleting 2 yields a total of 6 points. Handle arrays up to length 2 * 10^4 with values up to 10^4.

Examples

Example 1

Input: nums = [3,4,2]

Output: 6

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

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 * 104
1 <= nums[i] <= 104

Solution Approach

Transform array into value-frequency map

Create a hash map where each key is a number from the array and the value is the sum of all occurrences of that number. This converts the problem into a variant of House Robber dynamic programming, reducing redundant scans.

Apply dynamic programming

Sort the unique numbers and iterate, maintaining two states: take or skip the current number. If you take it, add its total points to the maximum from numbers not adjacent. If you skip, carry forward the previous maximum. This guarantees optimal selection without violating adjacency.

Return the final maximum points

After iterating through all unique numbers, the DP state representing the maximum points when considering the last number gives the answer. This ensures the sum of selected numbers is maximized while respecting the deletion rule.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k log k) where n is the array length and k is the number of unique values due to map construction and sorting. Space complexity is O(k) for the map and DP arrays.

What Interviewers Usually Probe

Checks if you recognize this is similar to the House Robber pattern using array scanning plus hash lookup.
Wants awareness of adjacency deletion impact and efficient aggregation per value.
Evaluates if you convert raw array input into a DP-ready format instead of naive recursive deletion.

Common Pitfalls or Variants

Common pitfalls

Failing to combine all identical numbers before DP, leading to suboptimal picks.
Ignoring that deleting a number affects adjacent numbers, causing off-by-one errors in totals.
Attempting naive recursion or repeated scanning, resulting in TLE for large arrays.

Follow-up variants

Allow negative numbers, requiring offset mapping for hash array indexing.
Provide nums as a stream, requiring online aggregation before DP.
Modify to delete k-adjacent values instead of 1-adjacent, adjusting DP recurrence.

FAQ

What is the core pattern behind Delete and Earn?

The pattern is similar to House Robber: selecting numbers while avoiding adjacent values, implemented with array scanning plus hash lookup.

How do you handle multiple occurrences of the same number?

Sum all occurrences into a hash map so that picking a number once accounts for its total value, simplifying the DP step.

Can this approach handle large arrays efficiently?

Yes, transforming to a value-frequency map and using DP ensures O(n + k log k) time, suitable for arrays up to 2 * 10^4 elements.

Why not delete numbers in arbitrary order?

Arbitrary deletion can remove high-value numbers incorrectly, violating the adjacency rule and producing suboptimal total points.

Does this method apply if numbers are negative or very large?

Yes, but negative numbers require offset mapping for array indexing and large values might require careful data structures to prevent overflow.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        mx = -inf
        for num in nums:
            mx = max(mx, num)
        total = [0] * (mx + 1)
        for num in nums:
            total[num] += num
        first = total[0]
        second = max(total[0], total[1])
        for i in range(2, mx + 1):
            cur = max(first + total[i], second)
            first = second
            second = cur
        return second

Continue Practicing

#691 stickers to spell word #792 number of matching subsequences #823 binary trees with factors