Delete and Earn — Solution in Python, Java & C++
Delete and Earn solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and hash table.
Delete and Earn is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Adobe and Morgan Stanley interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming
- Asked at: Amazon, Google, Adobe, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. You want to maximise the points you earn by repeatedly doing this:
- Pick any
nums[i]and earnnums[i]points. You must then delete every element equal tonums[i] - 1and every element equal tonums[i] + 1.
Return the maximum number of points you can earn.
Example 1
Input: nums = [3,4,2]
Output: 6
Explanation: Take 4 (earning 4), which deletes the 3; then take 2.
Example 2
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: Take the three 3s for 9; the 2s and the 4 are deleted.
Example 3
Input: nums = [1]
Output: 1
Constraints
1 <= nums.length <= 401 <= nums[i] <= 100
Hints for Delete and Earn
Hint 1
Taking one copy of a value means taking all copies — they never conflict with each other.
Hint 2
So collapse the array into
points[v] = v × count(v), indexed by value.Hint 3
Now adjacent values conflict, and the problem is exactly House Robber over that points array.
How to solve Delete and Earn
Taking a value means taking every copy of it, so collapse the array into points[v] = v · count(v). Adjacent values conflict, and the problem is House Robber over that array.
Approach
- Build
pointsindexed by value. - Walk values from 1 to
max:take = skip + points[v],skip = max(skip, take_prev). - Return
max(take, skip).
Why it works
Copies of the same value never delete each other, so choosing a value is all-or-nothing. Choosing v forbids v ± 1 and nothing else, which is exactly the no-two-adjacent constraint the rolling take/skip pair solves optimally.
Complexity
- Time —
O(n + max) - Space —
O(max)
Pitfalls
- A sorted map of distinct values handles sparse large values; the dense array is simplest when the range is small.
Reference solution
Python
def deleteAndEarn(nums) -> int:
max_v = max(nums)
points = [0] * (max_v + 1)
for x in nums:
points[x] += x
take = skip = 0
for v in range(1, max_v + 1):
take, skip = skip + points[v], max(skip, take)
return max(take, skip)Java
public static int deleteAndEarn(int[] nums) {
int maxV = 0;
for (int x : nums) maxV = Math.max(maxV, x);
int[] points = new int[maxV + 1];
for (int x : nums) points[x] += x;
int take = 0, skip = 0;
for (int v = 1; v <= maxV; v++) {
int newTake = skip + points[v];
int newSkip = Math.max(skip, take);
take = newTake;
skip = newSkip;
}
return Math.max(take, skip);
}C++
int deleteAndEarn(vector<int>& nums) {
int maxV = 0;
for (int x : nums) maxV = max(maxV, x);
vector<int> points(maxV + 1, 0);
for (int x : nums) points[x] += x;
int take = 0, skip = 0;
for (int v = 1; v <= maxV; v++) {
int newTake = skip + points[v];
int newSkip = max(skip, take);
take = newTake;
skip = newSkip;
}
return max(take, skip);
}JavaScript
var deleteAndEarn = function(nums) {
let maxV = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > maxV) maxV = nums[i];
}
const points = new Array(maxV + 1).fill(0);
for (let i = 0; i < nums.length; i++) points[nums[i]] += nums[i];
let take = 0, skip = 0;
for (let v = 1; v <= maxV; v++) {
const newTake = skip + points[v];
const newSkip = Math.max(skip, take);
take = newTake;
skip = newSkip;
}
return Math.max(take, skip);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets