algoadvance

You are given an integer array nums. You want to maximize the amount 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. However, after picking nums[i], you must also delete every element equal to nums[i] - 1 and nums[i] + 1 from the array.

Your task is to return the maximum number of points you can earn by applying the above operation.

Example

• Example 1:
  • Input: nums = [3, 4, 2]
  • Output: 6
  • Explanation: Delete 4 to earn 4 points, resulting in nums = [3, 2]. Then, delete 2 to earn 2 points, resulting in nums = [3]. Then, delete 3 to earn 3 points, resulting in an empty list. You earn a total of 4 + 2 + 3 = 9 points.
• Example 2:
  • Input: nums = [2, 2, 3, 3, 3, 4]
  • Output: 9
  • Explanation: Delete 3 to earn 3 points, resulting in nums = [2, 2, 4]. Then, delete 3 to earn 3 points, resulting in nums = [2, 2, 4]. Then, delete 4 to earn 4 points, resulting in nums = [2, 2]. Now you can’t delete 2 anymore since there are no more 3s in the array. You earn a total of 3 + 3 + 4 = 9 points.

Clarifying Questions

1. Can the array nums be empty?
   • No.
2. What is the range of values for nums and its elements?
   • The length of the array is up to (10^4), and each element in nums can be between 1 and 10^4.

Strategy

The problem can be reduced to a variant of the “House Robber” problem. Here’s a detailed breakdown:

1. Frequency Mapping: First, we can use a dictionary to count the occurrences of each number in nums. This helps in calculating the total points we can earn from each unique number.

2. Convert Problem: Once we have the total points for each number, the problem converts to a dynamic programming problem similar to the house robber: should we “rob” this house (pick this number) or skip it (avoid picking this number and picking adjacent numbers).

3. Dynamic Programming Array: We’ll use a dp array where dp[i] will represent the maximum points we can earn considering numbers from 1 up to i.

4. State Transition: For each unique number, we can decide to either:
   • Take points including i and skip i-1, i.e., dp[i] = max(dp[i-1], points[i] + dp[i-2])
   • Skip the current number i, i.e., dp[i] = dp[i-1]

5. Initialize Base Cases: Start with initial conditions for dp[0] and dp[1].

6. Return Result: The maximum points achievable considering all numbers up to the maximum value in nums.

Code

def deleteAndEarn(nums):
    from collections import defaultdict
    
    if not nums:
        return 0

    # Calculate total points for each unique number
    points = defaultdict(int)
    for num in nums:
        points[num] += num
    
    # Create a sorted list of unique numbers
    unique_nums = sorted(points.keys())
    
    # Initialize dp array
    prev2 = 0
    prev1 = points[unique_nums[0]]
    
    for i in range(1, len(unique_nums)):
        current = unique_nums[i]
        if unique_nums[i] == unique_nums[i-1] + 1:
            current_points = max(prev1, prev2 + points[current])
        else:
            current_points = prev1 + points[current]
        
        prev2, prev1 = prev1, current_points
    
    return prev1

# Example usages
print(deleteAndEarn([3, 4, 2]))       # Output: 6
print(deleteAndEarn([2, 2, 3, 3, 3, 4]))  # Output: 9

Time Complexity

• Constructing the frequency dictionary takes (O(n)).
• Sorting the unique elements takes (O(k \log k)), where (k) is the number of unique elements (maximum (10^4)).
• Iterating through the sorted elements and computing dp values takes (O(k)).

Thus, the overall time complexity is (O(n + k \log k)).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?