Delete and Earn

103.3k
0

An integer array nums is given. An operation selects one element with value x, deletes the selected element, and earns x points. Every remaining element equal to (x - 1 ) or (x + 1 ) must also be deleted after the selection.

Any number of operations may be performed. Return the maximum total points obtainable.

Example 1

Input: nums = [2, 2, 3, 4, 4]
Output: 12
Explanation: Both occurrences of 2 provide 4 points, and both occurrences of 4 provide 8 points. Values 2 and 4 do not conflict, so the best total equals 4 + 8 = 12.

Example 2

Input: nums = [8]
Output: 8
Explanation: The single value provides 8 points without removing another available value.

Recursion

Equal values never block one another. Choosing value x leaves every other copy of x available, so all copies can be grouped into one reward bucket named points[x]. After grouping, taking bucket x blocks only bucket x - 1. The resulting choice matches the House Robber pattern.

The state solve(value) stores the best score available from bucket 0 through bucket value. A recursive call either skips the current bucket or takes the current bucket and moves past the adjacent bucket. The first call starts from state maxValue because the complete reward range ends at the largest bucket.

Algorithm

  • Find the maximum array value maxValue so every possible reward bucket receives a valid index.

  • Build a points array through maxValue, adding each number x to points[x] so equal values form one combined reward.

  • Define solve(value) as the best score through value, allowing every recursive state to describe one smaller prefix of reward buckets.

  • Return 0 for state 0 and points[1] for state 1 because both smallest ranges have only one possible best total.

  • Compute the skip score from solve(value - 1) because rejecting the current bucket preserves the full smaller range.

  • Compute the take score from points[value] + solve(value - 2) because taking the current bucket removes the adjacent bucket.

  • Return the larger score and start from maxValue so recursion compares every valid take-or-skip combination in the complete range.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best score through one value.
int solve(int value, vector<int>& points) {
// No reward remains below the first bucket.
if (value == 0) {
return 0;
}
// Bucket one is the only available bucket.
if (value == 1) {
return points[1];
}
// Skipping keeps the complete smaller range.
int skip = solve(value - 1, points);
// Taking removes the adjacent reward bucket.
int take = points[value] + solve(value - 2, points);
// The larger valid choice gives the best score.
return max(skip, take);
}
public:
// Returns the maximum obtainable score.
int deleteAndEarn(vector<int>& nums) {
// The maximum value sets the final bucket.
int maxValue = *max_element(nums.begin(), nums.end());
// Every index stores one combined reward.
vector<int> points(maxValue + 1, 0);
// Equal values join the same reward bucket.
for (int number : nums) {
points[number] += number;
}
// The largest state covers the complete range.
return solve(maxValue, points);
}
};
// Driver code
int main() {
vector<int> nums = {2, 2, 3, 4, 4};
Solution obj;
cout << obj.deleteAndEarn(nums);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(n + 2M), reward aggregation scans n elements, while two recursive choices can branch across a depth of M values.

Space Complexity: O(M), the points array spans the value range and the recursion stack can reach M calls.

Memoization

Direct recursion reaches the same smaller bucket range from several branches. A completed result for solve(value) never changes, so repeated evaluation adds work without adding information.

Memoization adds a dp array for saved results. Every uncached state keeps the same take-or-skip decision, while every cached state returns immediately. The recurrence and the starting state remain unchanged.

Algorithm

  • Build the same points array through maxValue so reward aggregation preserves the recursive state meaning.

  • Create a dp array filled with -1 so every untouched position clearly marks an uncalculated state.

  • Keep the base results for states 0 and 1 because the two smallest ranges need no further branching.

  • Return dp[value] whenever a saved result exists, avoiding repeated exploration of an identical bucket prefix.

  • Compute the skip score from state value - 1 because rejecting the current bucket leaves every smaller bucket available.

  • Compute the take score from state value - 2 and add points[value] because the adjacent bucket becomes unavailable.

  • Store the larger score in dp[value] before returning, allowing later branches to reuse the completed answer.

Dry Run

Delete and Earn Memoization

Delete and Earn Memoization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the cached score through one value.
int solve(int value, vector<int>& points, vector<int>& dp) {
// No reward remains below the first bucket.
if (value == 0) {
return 0;
}
// Bucket one is the only available bucket.
if (value == 1) {
return points[1];
}
// A saved state avoids repeated branching.
if (dp[value] != -1) {
return dp[value];
}
// Skipping keeps the complete smaller range.
int skip = solve(value - 1, points, dp);
// Taking removes the adjacent reward bucket.
int take = points[value] + solve(value - 2, points, dp);
// The larger valid choice is saved for reuse.
dp[value] = max(skip, take);
// The cached value represents the full state.
return dp[value];
}
public:
// Returns the maximum obtainable score.
int deleteAndEarn(vector<int>& nums) {
// The maximum value sets the final bucket.
int maxValue = *max_element(nums.begin(), nums.end());
// Every index stores one combined reward.
vector<int> points(maxValue + 1, 0);
// Equal values join the same reward bucket.
for (int number : nums) {
points[number] += number;
}
// Negative one marks every uncalculated state.
vector<int> dp(maxValue + 1, -1);
// The largest state covers the complete range.
return solve(maxValue, points, dp);
}
};
// Driver code
int main() {
vector<int> nums = {2, 2, 3, 4, 4};
Solution obj;
cout << obj.deleteAndEarn(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(n + M), reward aggregation scans n elements and memoization evaluates each of the M + 1 states once.

Space Complexity: O(M), the points and dp arrays span the value range and the recursion stack can reach M calls.

Tabulation

Memoization begins at the largest bucket and reaches smaller states through recursive calls. Tabulation reverses the evaluation order and fills the same answers from the smallest bucket upward, removing recursion-stack work.

At bucket value, both required answers are already available. The entry dp[value - 1] supports a skip, while points[value] + dp[value - 2] supports a take. Increasing order keeps both dependencies ready before every update.

Algorithm

  • Build points through maxValue so every equal-value group contributes one reward to the same indexed bucket.

  • Create a dp array through maxValue so dp[value] can store the best score for the prefix ending at value.

  • Keep dp[0] = 0 and set dp[1] = points[1] because the two smallest prefixes have direct answers.

  • Process values from 2 through maxValue in increasing order so both earlier states are complete before every transition.

  • Read the skip score from dp[value - 1] because rejecting the current bucket preserves the previous best total.

  • Form the take score from points[value] + dp[value - 2] because taking the current bucket blocks only the adjacent bucket.

  • Store the larger score in dp[value] and return dp[maxValue] so the final entry represents the complete reward range.

Dry Run

Delete and Earn Tabulation

Delete and Earn Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum obtainable score.
int deleteAndEarn(vector<int>& nums) {
// The maximum value sets the final bucket.
int maxValue = *max_element(nums.begin(), nums.end());
// Every index stores one combined reward.
vector<int> points(maxValue + 1, 0);
// Equal values join the same reward bucket.
for (int number : nums) {
points[number] += number;
}
// Every entry stores one completed prefix score.
vector<int> dp(maxValue + 1, 0);
// Bucket one forms the first positive prefix.
dp[1] = points[1];
// Increasing order keeps both dependencies ready.
for (int value = 2; value <= maxValue; value++) {
// Skipping preserves the previous best score.
int skip = dp[value - 1];
// Taking adds the best non-adjacent prefix.
int take = points[value] + dp[value - 2];
// The larger valid choice completes the state.
dp[value] = max(skip, take);
}
// The last entry covers the complete value range.
return dp[maxValue];
}
};
// Driver code
int main() {
vector<int> nums = {2, 2, 3, 4, 4};
Solution obj;
cout << obj.deleteAndEarn(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(n + M), reward aggregation visits n elements and tabulation fills M + 1 bucket states once.

Space Complexity: O(M), the points and dp arrays each span the complete value range without recursion-stack storage.

Space Optimization

Tabulation reads only the previous two dp entries while building a new answer. Older entries never contribute again, so two rolling variables can replace the full dp array.

The variable previousTwo represents dp[value - 2], and previousOne represents dp[value - 1]. The current score is calculated before either saved value moves forward, preserving both dependencies for the take-or-skip comparison.

Algorithm

  • Build the same points array through maxValue because reward aggregation remains necessary after removal of the dp array.

  • Set previousTwo = 0 for the prefix through value 0, preserving the tabulation base state in one variable.

  • Set previousOne = points[1] for the prefix through value 1, keeping the second base state ready for value 2.

  • Process values from 2 through maxValue in increasing order so both rolling variables match the required earlier states.

  • Calculate current as the larger of previousOne and points[value] + previousTwo, preserving the same skip-or-take transition.

  • Shift previousTwo to the old previousOne and previousOne to current so the next iteration receives consecutive DP states.

  • Return previousOne after the final bucket because the latest rolling value represents the complete reward range.

Dry Run

Delete and Earn Space Optimization

Delete and Earn Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum obtainable score.
int deleteAndEarn(vector<int>& nums) {
// The maximum value sets the final bucket.
int maxValue = *max_element(nums.begin(), nums.end());
// Every index stores one combined reward.
vector<int> points(maxValue + 1, 0);
// Equal values join the same reward bucket.
for (int number : nums) {
points[number] += number;
}
// Two variables preserve the required DP states.
int previousTwo = 0;
int previousOne = points[1];
// Increasing order keeps both dependencies ready.
for (int value = 2; value <= maxValue; value++) {
// The current score keeps the better choice.
int current = max(
previousOne,
points[value] + previousTwo
);
// State shifts prepare the next bucket.
previousTwo = previousOne;
previousOne = current;
}
// The latest state covers the complete range.
return previousOne;
}
};
// Driver code
int main() {
vector<int> nums = {2, 2, 3, 4, 4};
Solution obj;
cout << obj.deleteAndEarn(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(n + M), reward aggregation visits n elements and the rolling transition processes M + 1 bucket states once.

Space Complexity: O(M), the points array spans the value range while the dynamic programming state uses only O(1) additional space.

Interview follow-up Questions

No. One operation collects only a single copy. However, equal values can be grouped together because deleting a value affects only its adjacent values, not its equal copies. Therefore, all copies of value x can be represented by their total contribution x × frequency[x].

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or secon...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0