740. Delete and Earn
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 takei
.nonSelect[i]
: the maximum sum you can obtain if you decide not to takei
.
The state transitions work as follows:
- If you take the number
i
, you couldn't have takeni - 1
, so your current maximum if you selecti
is the maximum of not selectingi - 1
plus the sum ofi
. - If you don't take
i
, the maximum is the larger of the previous maxima regardless of whetheri - 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 thetotal
array, which is analogous to thesums
array in the reference approach. Thistotal
array holds the aggregate points that each number contributes. -
Calculating total points for each number:
- We initialize the
total
array with the sizemx + 1
(since arrays are 0-indexed). - We iterate through the
nums
array once again to sum the points for each number. For eachnum
innums
, we addnum
tototal[num]
, which is adding the points for each occurrence of that number.
- We initialize the
-
Dynamic Programming (DP) State Transition:
- We define two states,
first
andsecond
. Respectively, they correspond tononSelect
andselect
for two consecutive elements being processed in a DP manner. In the reference approach,select
andnonSelect
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.
- We define two states,
-
Iterative Optimization:
- We start iterating from 2 to
mx
(inclusive) to update thefirst
andsecond
states:- For each number
i
, the current maximum pointscur
when choosing the numberi
is computed asmax(first + total[i], second)
which follows the transition:- If we choose
i
, we add the points from choosingi
(total[i]
) to the maximum points without includingi-1
(first
). This reflects the concept that if we are taking numberi
, we must have not takeni-1
. - If we don't choose
i
, the maximum stays atsecond
which is the larger of the previous maxima irrespective of whetheri-1
was chosen or not.
- If we choose
- We then update
first
andsecond
for the next iteration:first
gets the value ofsecond
.second
gets the value ofcur
.
- For each number
- We start iterating from 2 to
-
Returning the Result:
- After the loop,
second
will hold the maximum number of points that can be achieved from0
tomx
, as it either includes or excludes the last number. Therefore, we returnsecond
as the solution.
- After the loop,
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 EvaluatorExample 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 is4
.
- We find the maximum number in
-
Calculating total points for each number:
- We initialize the
total
array with a length of5
(0-indexed, so we go from0
to4
). - By iterating through
nums
, we calculate thetotal
as follows:total[2]
would be4
(because there are two2's
and2*2=4
).total[3]
would be6
(two3's
, so3*2=6
).total[4]
would be8
(two4's
, so4*2=8
).
- We initialize the
-
Dynamic Programming (DP) State Transition:
- Initialize
first = total[0]
which is0
(no contribution from the number 0). - Initialize
second = max(total[0], total[1])
which ismax(0, 0)
because the number1
does not appear innums
. Thus,second
is0
.
- Initialize
-
Iterative Optimization:
- For
i=2
, we calculatecur = max(first + total[2], second)
which ismax(0+4, 0)
resulting incur = 4
. Updatefirst
to0
(previoussecond
) andsecond
to4
. - For
i=3
, we calculatecur = max(first + total[3], second)
which ismax(0+6, 4)
resulting incur = 6
. Updatefirst
to4
andsecond
to6
. - For
i=4
, we calculatecur = max(first + total[4], second)
which ismax(4+8, 6)
resulting incur = 12
. Updatefirst
to6
andsecond
to12
.
- For
-
Returning the Result:
- The loop ends with
second
being12
, which signifies that by following the described selection process, we have maximally earned12
points.
- The loop ends with
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 innums
, which takesO(N)
. - The second
for
loop creates thetotal
array by summing the value of each number where thenum
appears. This also takesO(N)
time as it iterates over all elements innums
. - The third
for
loop iterates over the range from2
tomx
, to calculate the maximum points that can be earned without adjacent numbers. This runs inO(M)
time, whereM
is the maximum number innums
.
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 ofmx + 1
, accounting for all numbers from0
tomx
inclusive. - Constant space for variables
first
,second
,cur
, andmx
.
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.
Which of the following array represent a max heap?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!