740. Delete and Earn

MediumArrayHash TableDynamic Programming

Problem Description

In this problem, you're given an array of integers called nums, where each element represents points you can earn. The goal is to accumulate the highest number of points possible by repeatedly performing a specific operation.

The operation consists of the following steps:

Choose any element from the array (nums[i]) and earn points equal to its value (nums[i] points).
Once you've earned points from nums[i], you must then delete every element from the array that is either 1 less (nums[i] - 1) or 1 more (nums[i] + 1) than the chosen element.

You can repeat this operation as many times as you wish in order to maximize your points. The challenge resides in selecting the elements in an order that prevents you from eliminating potential points that could have been earned later on.

The task is to determine the maximum number of points you can earn by applying the operation optimally.

Intuition

The key observation to solve this problem is recognizing that if you choose any number, you should take all instances of that number because choosing one instance will force you to delete the others anyway.

To approach this, you can leverage dynamic programming. The first step is to create an array, sums, to accumulate the total sum of points that each unique number in nums can contribute. Essentially, for each value i, sums[i] holds the total points from all occurrences of i in nums.

Now, since you cannot pick numbers adjacent to each other (i.e., nums[i], nums[i]-1, and nums[i]+1 are mutually exclusive choices), you should maintain two states:

select[i]: the maximum sum you can obtain if you choose to take i.
nonSelect[i]: the maximum sum you can obtain if you decide not to take i.

The state transitions work as follows:

If you take the number i, you couldn't have taken i - 1, so your current maximum if you select i is the maximum of not selecting i - 1 plus the sum of i.
If you don't take i, the maximum is the larger of the previous maxima regardless of whether i - 1 was selected or not.

The relationship can then be defined as:

select[i] = nonSelect[i - 1] + sums[i]
nonSelect[i] = max(select[i - 1], nonSelect[i - 1])

The solution iterates over the values, updating select and nonSelect based on the points from sums. The final solution will be the maximum value between choosing and not choosing the last element in the array.

The given Python solution implements this using a simplified dynamic programming approach with a single array, total, which plays the role of sums, and two variables, first and second, to keep track of the select and nonSelect states for the last two processed numbers. The approach ensures that the solution is derived efficiently with optimal space usage.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution follows a bottom-up dynamic programming approach where the operation of choosing a number encompasses a couple of algorithms and data structures to reach an optimal solution.

Pre-processing step: We go through the nums array to find the maximum number (mx) among all the numbers, as it will determine the size of the total array, which is analogous to the sums array in the reference approach. This total array holds the aggregate points that each number contributes.
Calculating total points for each number:
- We initialize the total array with the size mx + 1 (since arrays are 0-indexed).
- We iterate through the nums array once again to sum the points for each number. For each num in nums, we add num to total[num], which is adding the points for each occurrence of that number.
Dynamic Programming (DP) State Transition:
- We define two states, first and second. Respectively, they correspond to nonSelect and select for two consecutive elements being processed in a DP manner. In the reference approach, select and nonSelect arrays are used, while in the solution code we only use two variables for space optimization.
- Initialize these variables as follows:
  - first = total[0], as this is the point contribution for the number 0.
  - second = max(total[0], total[1]), as this is the maximum between choosing 0 and choosing 1 but not choosing 0.
Iterative Optimization:
- We start iterating from 2 to mx (inclusive) to update the first and second states:
  - For each number i, the current maximum points cur when choosing the number i is computed as max(first + total[i], second) which follows the transition:
    - If we choose i, we add the points from choosing i (total[i]) to the maximum points without including i-1 (first). This reflects the concept that if we are taking number i, we must have not taken i-1.
    - If we don't choose i, the maximum stays at second which is the larger of the previous maxima irrespective of whether i-1 was chosen or not.
  - We then update first and second for the next iteration:
    - first gets the value of second.
    - second gets the value of cur.
Returning the Result:
- After the loop, second will hold the maximum number of points that can be achieved from 0 to mx, as it either includes or excludes the last number. Therefore, we return second as the solution.

By employing this dynamic programming technique, the problem avoids brute-force repetitions and overcomes the potential exponential time complexity we would face if we tried every possible combination of elements to delete from the nums array. This implementation ensures that the solution is reached in O(n + k) time, where 'n' is the length of nums and 'k' is the range of numbers in nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small input array nums containing the following elements: [3, 4, 2, 2, 3, 4].

Pre-processing step:
- We find the maximum number in nums, which is 4.
Calculating total points for each number:
- We initialize the total array with a length of 5 (0-indexed, so we go from 0 to 4).
- By iterating through nums, we calculate the total as follows:
  - total[2] would be 4 (because there are two 2's and 2*2=4).
  - total[3] would be 6 (two 3's, so 3*2=6).
  - total[4] would be 8 (two 4's, so 4*2=8).
Dynamic Programming (DP) State Transition:
- Initialize first = total[0] which is 0 (no contribution from the number 0).
- Initialize second = max(total[0], total[1]) which is max(0, 0) because the number 1 does not appear in nums. Thus, second is 0.
Iterative Optimization:
- For i=2, we calculate cur = max(first + total[2], second) which is max(0+4, 0) resulting in cur = 4. Update first to 0 (previous second) and second to 4.
- For i=3, we calculate cur = max(first + total[3], second) which is max(0+6, 4) resulting in cur = 6. Update first to 4 and second to 6.
- For i=4, we calculate cur = max(first + total[4], second) which is max(4+8, 6) resulting in cur = 12. Update first to 6 and second to 12.
Returning the Result:
- The loop ends with second being 12, which signifies that by following the described selection process, we have maximally earned 12 points.

Therefore, for the array [3, 4, 2, 2, 3, 4], the maximum number of points that can be earned is 12.

Solution Implementation

1from typing import List
2
3class Solution:
4    def deleteAndEarn(self, nums: List[int]) -> int:
5        # Find the maximum value in nums array
6        max_value = max(nums)
7      
8        # Create a list to store the total points for each number
9        total_points = [0] * (max_value + 1)
10      
11        # Fill the total_points list where the index represents the number
12        # and the value at that index is the total points that can be earned from that number
13        for num in nums:
14            total_points[num] += num
15      
16        # Initialize first and second variables to store the
17        # total points earned up to the previous and current positions
18        earn_prev_prev = total_points[0]
19        earn_prev = max(total_points[0], total_points[1])
20      
21        # Iterate over the total_points list starting from the second index
22        for i in range(2, max_value + 1):
23            # Calculate the current max points by either taking the current number
24            # and the points from two steps before, or the points from the previous step
25            current_max = max(earn_prev_prev + total_points[i], earn_prev)
26          
27            # Update the points from two steps before and the previous step
28            earn_prev_prev = earn_prev
29            earn_prev = current_max
30      
31        # The last 'earn_prev' contains the maximum points that can be earned
32        return earn_prev
33

1public class Solution {
2  
3    // Method to calculate the maximum points you can earn by deleting elements
4    public int deleteAndEarn(int[] nums) {
5        // Return 0 if the array is empty
6        if (nums.length == 0) {
7            return 0;
8        }
9
10        // Create an array to store the sum of points for each number
11        int[] valueSums = new int[10010];
12        // Create an array to store the maximum points if we select the current number
13        int[] dpSelect = new int[10010];
14        // Create an array to store the maximum points if we do not select the current number
15        int[] dpNonSelect = new int[10010];
16
17        // Variable to store the maximum value in nums
18        int maxValue = 0;
19        // Populate the valueSums array and find the maximum value
20        for (int num : nums) {
21            valueSums[num] += num;
22            maxValue = Math.max(maxValue, num);
23        }
24
25        // Dynamic programming to decide whether to select or not select a particular number
26        for (int i = 1; i <= maxValue; i++) {
27            // If we select i, we can't use i-1, so we add the points of i to dpNonSelect[i-1]
28            dpSelect[i] = dpNonSelect[i - 1] + valueSums[i];
29            // If we don't select i, take the maximum points from the previous selection or non-selection
30            dpNonSelect[i] = Math.max(dpSelect[i - 1], dpNonSelect[i - 1]);
31        }
32        // The result is the max points of selecting or not selecting the highest value
33        return Math.max(dpSelect[maxValue], dpNonSelect[maxValue]);
34    }
35}
36

1class Solution {
2public:
3    // The deleteAndEarn function.
4    int deleteAndEarn(vector<int>& numbers) {
5        // We create vals with size enough to cover all potential
6        // input numbers, initializing with 0s. This will store the cumulative values.
7        vector<int> cumulativeValues(10001, 0);
8      
9        // Populate cumulativeValues so that each index's value is the sum
10        // of all the occurrences of that number in the numbers vector.
11        for (int num : numbers) {
12            cumulativeValues[num] += num;
13        }
14      
15        // Now we use our rob function to find the maximum amount we can earn
16        // following the delete and earn rule.
17        return rob(cumulativeValues);
18    }
19
20    // The rob function uses dynamic programming to find the maximum earnable amount.
21    int rob(vector<int>& values) {
22        // Initialize the two variables to keep track of two states:
23        // prevMax: the maximum amount we can get from [0...i-2]
24        // currentMax: the maximum amount we can get from [0...i-1]
25        int prevMax = 0, currentMax = values[0];
26
27        for (int i = 1; i < values.size(); ++i) {
28            // Calculate the new max amount that can be earned
29            // including the current number or by excluding it.
30            // c decides whether to take the current number or not.
31            int tempMax = max(values[i] + prevMax, currentMax);
32
33            // Move currentMax to prevMax for the next iteration, and
34            // update currentMax to the newly calculated tempMax.
35            prevMax = currentMax;
36            currentMax = tempMax;
37        }
38
39        // At the end, currentMax will contain the maximum amount that
40        // can be earned by either taking or skipping each number.
41        return currentMax;
42    }
43};
44

1// Define an array to represent the cumulative values of numbers.
2let cumulativeValues: number[] = new Array(10001).fill(0);
3
4// The deleteAndEarn function, which takes an array of numbers and returns the maximum points that can be earned.
5function deleteAndEarn(numbers: number[]): number {
6    // Populate cumulativeValues so that each index's value is the sum
7    // of all occurrences of that number in the input numbers array.
8    for (let num of numbers) {
9        cumulativeValues[num] += num;
10    }
11  
12    // Use the rob function to find the maximum amount we can earn
13    // following the delete and earn rule.
14    return rob(cumulativeValues);
15}
16
17// The rob function uses dynamic programming to calculate the maximum earnable amount.
18function rob(values: number[]): number {
19    // Initialize variables to keep track of the two states:
20    // prevMax stores the maximum amount we can get from [0...i-2]
21    // currentMax stores the maximum amount we can get from [0...i-1]
22    let prevMax = 0;
23    let currentMax = values[0];
24  
25    for (let i = 1; i < values.length; i++) {
26        // Calculate the tempMax which is the new maximum amount that can 
27        // be earned by including or excluding the current number.
28        let tempMax = Math.max(values[i] + prevMax, currentMax);
29
30        // Update prevMax to the previous currentMax for the next iteration,
31        // and set currentMax to the newly calculated max (tempMax).
32        prevMax = currentMax;
33        currentMax = tempMax;
34    }
35  
36    // currentMax will hold the maximum amount that can be earned 
37    // after considering all the numbers.
38    return currentMax;
39}
40

Time and Space Complexity

The provided code is designed to solve the problem by first calculating the maximum value in the list of numbers, creating an array that sums the same elements' values, and then using a dynamic programming approach similar to the house robber problem. The complexities are as follows:

Time Complexity

The time complexity of the algorithm is O(N + M), where N is the length of the nums array and M is the maximum number in the nums. This is because:

The first for loop which calculates the maximum number, mx, iterates over all elements in nums, which takes O(N).
The second for loop creates the total array by summing the value of each number where the num appears. This also takes O(N) time as it iterates over all elements in nums.
The third for loop iterates over the range from 2 to mx, to calculate the maximum points that can be earned without adjacent numbers. This runs in O(M) time, where M is the maximum number in nums.

Therefore, adding these up we get O(N) + O(N) + O(M) which simplifies to O(N + M) as the dominant terms.

Space Complexity

The space complexity of the algorithm is O(M), where M is the maximum number in nums. This is due to:

The total array, which has a length of mx + 1, accounting for all numbers from 0 to mx inclusive.
Constant space for variables first, second, cur, and mx.

Therefore, the additional space used by the algorithm is predominated by the size of the total array.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know