Problem Description

You have an integer array nums and want to maximize your points through a strategic deletion process.

The rules are:

• You can pick any element nums[i] from the array and delete it, earning nums[i] points
• When you delete nums[i], you must also delete ALL elements with value nums[i] - 1 and ALL elements with value nums[i] + 1 from the array (without earning points for these forced deletions)
• You can repeat this operation as many times as you want with the remaining elements

Your goal is to find the maximum total points you can earn.

For example, if nums = [3, 4, 2]:

• If you delete 4, you earn 4 points but must also remove all 3s and 5s (the 3 gets removed without earning points)
• You're left with [2], which you can delete for 2 more points
• Total: 4 + 2 = 6 points

The challenge is determining which elements to delete and in what order to maximize your total score, considering that choosing certain values forces you to sacrifice adjacent values.

Intuition

The key insight is that when we choose to take a number x, we automatically forfeit all instances of x-1 and x+1. This means we face a choice: either take all occurrences of x (earning x * count(x) points) or skip x entirely.

Since we can't take consecutive numbers, this problem transforms into something familiar. If we group all identical numbers together and calculate their total value, we get an array where total[i] represents the sum of all occurrences of number i.

For example, if nums = [2, 2, 3, 3, 3, 4]:

• total[2] = 4 (two 2's)
• total[3] = 9 (three 3's)
• total[4] = 4 (one 4)

Now the problem becomes: given an array where we can't pick adjacent elements, what's the maximum sum we can achieve? This is the classic "House Robber" problem!

At each number i, we have two choices:

1. Take number i: We get total[i] points plus the best we could do up to i-2 (since we can't take i-1)
2. Skip number i: We keep the best result up to i-1

We choose whichever gives more points: max(total[i] + dp[i-2], dp[i-1])

This dynamic programming approach naturally handles the constraint that picking a number eliminates its neighbors, while ensuring we maximize our total score.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation follows our intuition of transforming this into a House Robber problem:

Step 1: Find the maximum value and create frequency sum array

mx = -inf
for num in nums:
    mx = max(mx, num)
total = [0] * (mx + 1)

We first find the maximum value in nums to determine the size of our total array. The total array will store the sum of all occurrences for each number from 0 to mx.

Step 2: Calculate total points for each number

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

For each number in the original array, we add its value to total[num]. If number 3 appears four times, total[3] will be 12.

Step 3: Apply House Robber dynamic programming

first = total[0]
second = max(total[0], total[1])

We initialize two variables:

• first: Maximum points we can get considering elements up to index i-2
• second: Maximum points we can get considering elements up to index i-1

Step 4: Iterate through remaining numbers

for i in range(2, mx + 1):
    cur = max(first + total[i], second)
    first = second
    second = cur

For each position i:

• Calculate cur = max(first + total[i], second)
  • first + total[i]: Take current number (add to best result from i-2)
  • second: Skip current number (keep best result from i-1)
• Update variables for next iteration: first becomes old second, second becomes cur

Step 5: Return the result

return second

The final second contains the maximum points achievable.

This space-optimized approach uses O(max_value) space and O(n + max_value) time, where n is the length of the input array.

Example Walkthrough

Let's walk through the solution with nums = [2, 2, 3, 3, 3, 4]:

Step 1: Find maximum value and create frequency sum array

• Maximum value in nums is 4
• Create total array of size 5: [0, 0, 0, 0, 0]

Step 2: Calculate total points for each number

• Process each number in nums:
  • Two 2's: total[2] = 2 + 2 = 4
  • Three 3's: total[3] = 3 + 3 + 3 = 9
  • One 4: total[4] = 4
• Result: total = [0, 0, 4, 9, 4]

Step 3: Initialize House Robber variables

• first = total[0] = 0 (best we can do up to index 0)
• second = max(total[0], total[1]) = max(0, 0) = 0 (best up to index 1)

Step 4: Dynamic programming iteration

i = 2:

• cur = max(first + total[2], second) = max(0 + 4, 0) = 4
• We take all 2's (worth 4 points)
• Update: first = 0, second = 4

i = 3:

• cur = max(first + total[3], second) = max(0 + 9, 4) = 9
• We take all 3's (worth 9 points), which means we can't take 2's or 4's
• Update: first = 4, second = 9

i = 4:

• cur = max(first + total[4], second) = max(4 + 4, 9) = max(8, 9) = 9
• We skip 4's and keep our previous best of 9 (from taking all 3's)
• Update: first = 9, second = 9

Step 5: Return result

• Return second = 9

The optimal strategy is to delete all instances of 3, earning 9 points total. We cannot take 2's or 4's because they are adjacent to 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n is the length of the input array nums and m is the maximum value in nums.

• Finding the maximum value: O(n) - iterates through all elements once
• Building the total array: O(n) - iterates through all elements to accumulate sums
• Dynamic programming loop: O(m) - iterates from index 2 to mx
• Overall: O(n) + O(n) + O(m) = O(n + m)

Space Complexity: O(m) where m is the maximum value in nums.

• The total array: O(m + 1) = O(m) - creates an array of size mx + 1
• Additional variables (first, second, cur): O(1)
• Overall: O(m)

Note: In the worst case where m is significantly larger than n (e.g., nums = [1, 10000]), the algorithm becomes inefficient. An alternative approach using a hash map or sorting could achieve O(n log n) time complexity with O(n) space complexity, which would be more efficient when m >> n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Out of Bounds When max_value is 0 or 1

The most critical pitfall in this solution is accessing points[1] when the maximum value in the array is 0. This causes an IndexError.

Problematic Code:

prev = max(points[0], points[1])  # Fails if max_value is 0

Example Case That Breaks:

• Input: nums = [0, 0, 0]
• max_value = 0, so points array has length 1
• Accessing points[1] throws IndexError

Solution: Add boundary condition checking:

# After creating points array
if max_value == 0:
    return points[0]
  
prev_prev = points[0]
prev = max(points[0], points[1]) if max_value >= 1 else points[0]

2. Memory Limit Exceeded for Large Sparse Values

When the input contains very large numbers that are sparsely distributed, the solution creates unnecessarily large arrays.

Problematic Scenario:

• Input: nums = [1, 2, 1000000]
• Creates an array of size 1,000,001 for just 3 unique values
• Wastes memory and time iterating through empty indices

Solution: Use a hash map approach with sorted unique values:

def deleteAndEarn(self, nums: List[int]) -> int:
    if not nums:
        return 0
  
    # Use Counter to get frequency of each number
    from collections import Counter
    count = Counter(nums)
    unique_nums = sorted(count.keys())
  
    # DP on unique values only
    n = len(unique_nums)
    dp = [0] * n
    dp[0] = unique_nums[0] * count[unique_nums[0]]
  
    for i in range(1, n):
        curr_val = unique_nums[i]
        curr_points = curr_val * count[curr_val]
      
        # Check if previous unique number is adjacent
        if unique_nums[i-1] == curr_val - 1:
            # Adjacent: can't take both
            take = curr_points + (dp[i-2] if i >= 2 else 0)
            skip = dp[i-1]
            dp[i] = max(take, skip)
        else:
            # Not adjacent: can take both
            dp[i] = dp[i-1] + curr_points
  
    return dp[n-1]

3. Integer Overflow in Points Calculation

While Python handles big integers automatically, in other languages or when optimizing, the sum calculation points[num] += num could overflow.

Problematic Case:

• Input: nums = [100000] * 100000
• points[100000] would be 10,000,000,000 (10 billion)

Solution: Check for potential overflow or use appropriate data types:

# Add overflow awareness (though Python handles this automatically)
MAX_SAFE_VALUE = 10**15  # Define reasonable limit
if points[num] > MAX_SAFE_VALUE - num:
    # Handle overflow case
    raise ValueError("Sum too large")
points[num] += num