Delete and Earn
Asked at Walmart
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.
Asked At
| 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).
Visual walkthrough for nums = [2,2,3,3,3,4]:
freq: {2:2, 3:3, 4:1}
points (for values 0-4): [0, 0, 4, 9, 4]
House Robber DP:
dp[0] = 0
dp[1] = max(0, 0) = 0
dp[2] = max(0, 0+4) = 4
dp[3] = max(4, 0+9) = 9
dp[4] = max(9, 4+4) = 9
Answer: 9 (take all 3s: earn 3*3=9)
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.