740. Delete and Earn
Asked at Walmart
Difficulty
Medium
Time
O(n + max_val)
Space
O(max_val)
Pattern
Array
Companies
1
Problem
You are given an integer array nums. You may repeat this operation as many times as you like: pick any element with value x, delete it, and gain x points. As a side effect, every remaining element equal to x - 1 and every element equal to x + 1 is also deleted (you earn nothing for those).
The goal is to collect the maximum total points possible. Return that maximum number.
The key rule that changes the answer: taking a value x blocks you from ever taking x - 1 or x + 1. But you can always take all copies of the same value x — each copy gives x points, and taking one copy does not remove the others. So the real decision is which values to take, not which individual elements.
Taking a value kills its neighbours
Constraints
- ●
1 <= nums.length <= 2 * 10^4 - ●
1 <= nums[i] <= 10^4
Examples
nums = [3,4,2]6nums = [2,2,3,3,3,4]9Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: for each element, try taking it or skipping it. When you take num, delete all (num-1) and (num+1). That's O(2^n) - exponential and too slow.
Key insight: group all occurrences of each number. If you take number x, you earn x * count(x), but you lose the ability to take (x-1) and (x+1). This is exactly the House Robber problem on a frequency array.
Why House Robber: create a points array where points[i] = i * count(i). You must maximize total points such that no two adjacent indices are both selected. The recurrence: dp[i] = max(dp[i-1], dp[i-2] + points[i]).
Step by step: (1) Count frequency of each number. (2) Build a points array where points[i] = i * freq[i]. (3) Apply House Robber DP on the points array. The max value is the answer.
Edge cases: single element (take it), all same elements (take all), consecutive elements from 1 to n (standard House Robber), large values (use frequency array of size max_val).
Optimal Approach
Step 1: Count the frequency of each number using a hash map.
Step 2: Create a points array of size max_val + 1 where points[i] = i * freq[i].
Step 3: Apply House Robber DP:
dp[0] = points[0]
dp[1] = max(points[0], points[1])
dp[i] = max(dp[i-1], dp[i-2] + points[i]) for i >= 2
Step 4: Return dp[max_val].
Walkthrough with nums = [2,2,3,3,3,4]:
freq = {2:2, 3:3, 4:1}
points = [0, 0, 4, 9, 4]dp[0] = 0dp[1] = max(0, 0) = 0dp[2] = max(dp[1], dp[0] + points[2]) = max(0, 0+4) = 4dp[3] = max(dp[2], dp[1] + points[3]) = max(4, 0+9) = 9dp[4] = max(dp[3], dp[2] + points[4]) = max(9, 4+4) = 9
Answer: 9. Take all three 3s for 9 points.
Time: O(n + max_val). Space: O(max_val).
Group by value, then House Robber
What Trips People Up in Real Interviews
Not recognizing the House Robber connection. Taking number x prevents taking (x-1) and (x+1) - that's the "no adjacent" constraint. Build a frequency-based points array and apply House Robber DP.
Trying to use a set or removing elements from the array. Modifying the input is expensive and error-prone. Instead, build the frequency/points array and use DP.
Forgetting to account for multiple occurrences. If nums = [3,3,3], deleting one 3 earns 3 points and removes all three 3s (9 total), not just one 3.
Using O(n^2) DP instead of recognizing the frequency optimization. The maximum value determines the DP array size, not the array length.
Off-by-one in the DP base cases. Handle max_val = 0 and max_val = 1 as edge cases before the loop.
Solution Code
O(n + max_val) timedef deleteAndEarn(nums):
from collections import Counter
freq = Counter(nums)
max_val = max(nums)
points = [0] * (max_val + 1)
for num, count in freq.items():
points[num] = num * count
if max_val == 0:
return points[0]
dp = [0] * (max_val + 1)
dp[0] = points[0]
dp[1] = max(points[0], points[1])
for i in range(2, max_val + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + points[i])
return dp[max_val]Frequently Asked Questions
What is the Delete and Earn problem?
Given an array of points, you can earn points by deleting an element and all elements equal to (num - 1) and (num + 1). Maximize your total points. This is a DP problem that transforms into the House Robber pattern.
How do you solve Delete and Earn?
The optimal approach runs in O(n + max_val) time and O(max_val) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Delete and Earn?
Delete and Earn is asked at Walmart. It is a medium difficulty problem.
What are common mistakes on Delete and Earn?
- Not recognizing the House Robber connection. Taking number x prevents taking (x-1) and (x+1) - that's the "no adjacent" constraint. Build a frequency-based points array and apply House Robber DP.
- Trying to use a set or removing elements from the array. Modifying the input is expensive and error-prone. Instead, build the frequency/points array and use DP.
- Forgetting to account for multiple occurrences. If `nums = [3,3,3]`, deleting one 3 earns 3 points and removes all three 3s (9 total), not just one 3.
- Using `O(n^2)` DP instead of recognizing the frequency optimization. The maximum value determines the DP array size, not the array length.
- Off-by-one in the DP base cases. Handle `max_val = 0` and `max_val = 1` as edge cases before the loop.