Delete and Earn

Medium

Salesforce

4 views

Topics:

Dynamic Programming

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

Return the maximum number of points you can earn by applying the above operation some number of times.

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: 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
Explanation: 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 * 10⁴
1 <= nums[i] <= 10⁴

Try coding it in LeetCode

Delete and Earn

Medium

Salesforce

4 views

Topics:

Dynamic Programming

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

Return the maximum number of points you can earn by applying the above operation some number of times.

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: 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
Explanation: 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 * 10⁴
1 <= nums[i] <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Can they be negative?
Can the input array be empty or null?
If there are multiple occurrences of the same number, do I earn points for each occurrence when I delete it?
Is there a specific ordering I need to consider when picking which numbers to delete first?
Are there any constraints on the size of the input array?

Brute Force Solution

Approach

The brute force strategy for this problem involves exploring every possible choice of number selection. We try every combination of taking or skipping each number and then calculating the total score. Finally, we pick the combination that gives us the biggest possible score.

Here's how the algorithm would work step-by-step:

Consider the first number. We have two options: either we pick it and add its value to our current score, or we skip it and move on.
If we pick a number, we must also remove any numbers that are one less or one more than the chosen number, as they become invalid.
After picking or skipping the first number, we move to the next available number and repeat the same two options: pick it and remove its neighbors, or skip it.
We continue this process, making a decision for each number until we've gone through all of them.
Each complete sequence of picks and skips results in a total score. We need to keep track of the highest score we've seen so far.
After exploring every possible sequence of picks and skips, the highest score we tracked represents the maximum points we can earn.

Code Implementation

def delete_and_earn_brute_force(numbers):
    maximum_score = 0

    def calculate_max_score(current_index, current_score, remaining_numbers):
        nonlocal maximum_score

        if current_index >= len(remaining_numbers):
            maximum_score = max(maximum_score, current_score)
            return

        # Option 1: Skip the current number
        calculate_max_score(current_index + 1, current_score, remaining_numbers)

        # Option 2: Pick the current number
        number_to_pick = remaining_numbers[current_index]

        # Create a new list excluding numbers +/- 1 of number_to_pick
        new_remaining_numbers = []

        # We have to rebuild the list of viable numbers after picking one
        for number_index in range(len(remaining_numbers)):
            if remaining_numbers[number_index] != number_to_pick - 1 and \
               remaining_numbers[number_index] != number_to_pick + 1:
                new_remaining_numbers.append(remaining_numbers[number_index])

        # Recursive call after picking a number
        calculate_max_score(
            0, current_score + number_to_pick, new_remaining_numbers
        )

    calculate_max_score(0, 0, numbers)
    return maximum_score

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of picking or skipping each number in the input array. For each of the n numbers, we have two choices, leading to 2 * 2 * ... * 2 (n times) possible paths. Therefore, the number of operations grows exponentially with the size of the input array, resulting in a time complexity of O(2^n).

Space Complexity

O(N) – The brute force solution described explores all possible combinations of picking or skipping numbers using recursion. The maximum depth of the recursion call stack would be proportional to the number of distinct numbers in the input array, which we can denote as N. Each recursive call requires a new stack frame. Therefore, the auxiliary space required for the recursion stack grows linearly with N, leading to O(N) space complexity.

Optimal Solution

Approach

This problem looks complicated, but it's actually a sneaky way to apply a simpler idea. Instead of deleting and earning, we reframe it as a choice: to take a number or leave it, and the earnings become points. This reduces to a common optimization problem.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list and store it as the points you get for picking that number.
Next, realize that you can't pick adjacent numbers, because the problem says you have to delete them. For example, if you pick 3, you can't pick 2 or 4.
Now, think about working your way up from small numbers to big numbers. At each number, you have a decision: either pick that number (and earn its points, but skip its neighbors) or don't pick that number (and keep your options open for later).
Keep track of the best score you can get up to each number, either by picking it or skipping it.
At the very end, the best score you can get up to the biggest number will be the answer to the original problem.

Code Implementation

def delete_and_earn(numbers: list[int]) -> int:
    points = {number: 0 for number in numbers}
    for number in numbers:
        points[number] += number

    max_number = max(numbers)
    take = 0
    skip = 0

    # Iterate through all possible numbers.
    for current_number in range(1, max_number + 1):
        # Decide to either take or skip.
        new_take = skip + points.get(current_number, 0)

        # Update take/skip values.
        new_skip = max(skip, take)

        take = new_take
        skip = new_skip

    # The maximum of take and skip at the end is the answer.
    return max(take, skip)

Big(O) Analysis

Time Complexity

O(n + m) – First, the algorithm counts the occurrences of each number in the input list of size n, which takes O(n) time. Then, the algorithm iterates through the possible numbers to consider, where m is the range of numbers (from the smallest to the largest number) in the input array. This iteration implicitly considers all unique numbers, and for each number, there are constant time operations. Therefore, the complexity becomes O(n + m) because we iterate through the input array and the possible numbers in the range.

Space Complexity

O(K) – The algorithm uses a dictionary or hash map to store the points for each unique number present in the input array. Let K be the number of distinct numbers in the input array. This hash map stores K key-value pairs, where each key is a unique number and the value is its corresponding point. Therefore, the auxiliary space used is proportional to the number of distinct elements in the input array, resulting in a space complexity of O(K).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as there are no elements to earn points from.
Input array with a single element	Return the value of the single element as that's the maximum possible score.
Input array with only two elements	Choose the larger element if the difference is greater than 1; otherwise, choose one of them or their sum.
Large input array with many duplicate elements	The algorithm should scale reasonably well with duplicates because it effectively groups identical values.
Input array with elements clustered around a specific value	Dynamic programming efficiently explores earning from or skipping each cluster.
Input array with a wide range of values (e.g., from 0 to 10000)	Using a hash map or frequency array can handle large ranges of non-negative integers efficiently.
Input contains a very large number of the same integer close to integer limit	Be mindful of potential integer overflow when calculating scores from sums of large integers.
Negative Numbers Present	The standard solution will not work with negative numbers unless you offset the values to convert them to non-negative.