740. Delete and Earn
On LeetCode ->Problem¶
Given positive integers, repeatedly earn a chosen value while removing every occurrence of its neighboring values. Return the maximum total score.
Key trick¶
Combine equal values into one reward, value * frequency; choosing that reward prevents choosing rewards at adjacent values, reducing the problem to House Robber.
Trap¶
- Once a value is selected, taking all its occurrences is always optimal.
- Conflicts depend on consecutive values, not consecutive positions.
- A DP state must preserve both taking and skipping possibilities; storing only the last chosen value loses valid solutions.
Why is it interesting?¶
A global-looking deletion process becomes a simple local dynamic program after aggregating equal values.
Python solution¶
class Solution:
def deleteAndEarn(self, nums: list[int]) -> int:
max_val = max(nums)
points = [0] * (max_val + 1)
# points[x] is the total reward from taking every occurrence of x.
for x in nums:
points[x] += x
prev2 = prev1 = 0
# Either skip x and keep prev1, or take x and add its reward to prev2.
for reward in points:
prev2, prev1 = prev1, max(prev1, prev2 + reward)
return prev1
Time complexity: \(O(n + M)\), where \(M = \max(\text{nums})\).
Space complexity: \(O(M)\).
Comment on my solution¶
Your House Robber insight and frequency aggregation are correct, but the tuple state discards the best score obtained by skipping the previous value.
For the failing case, when processing 5, the best compatible score is 3 from taking the 1s. Your prev2 instead contains 2 from taking 2, so it computes 2 + 15 = 17 rather than 3 + 15 = 18.
The recurrence should explicitly retain:
- The best score through the previous value.
- The best score through the value before it.
Also, the shown snippet requires an import for Counter.
# Ideas:
# - the order in which you pick matters
# - so the constraint seems to be global
# - how do we make it local or at least uses only few states
# - maybe sort the array first as we want to delete previous/next integer
# - It makes me think about the problem "burst balloon"
# - the trick here is to look at the last balloon to birst (instead of
# the first) in an
# interval, so separating into 2 disjoints interval problem
# - maybe use frequencies too
# - Once we look at the sorted numbers, the problem could be similar
# to "house robber" where we go from one house and we take or skip the
# house. In this case we only need 2 variables for the states.
# Wrong Answer: 26/52 testcases passed
# [1,1,1,2,4,5,5,5,6]
# Output: 17
# Expected: 18
class Solution:
def deleteAndEarn(self, nums: list[int]) -> int:
freqs = Counter(nums)
items = sorted(freqs.items())
prev2 = (0, float("-inf")) # (total, number we kept)
prev1 = (items[0][0] * items[0][1], items[0][0]) # (total, number we kept)
for x, freq in items[1:]:
prev2, prev1 = prev1, (max(prev2[0], prev1[0] if prev1[1] != x - 1 else 0) + x * freq, x)
return max(prev2[0], prev1[0])
Extra¶
Complement on my attempt¶
I don't see how "the best score obtained by skipping the previous value"? Can you modify my code (as little as possible) to make it work so I'll see what you mean.
Your code always adds x * freq, so prev1 represents a solution that takes the current value. It does not preserve the potentially better solution that skips it.
Here is your code with minimal changes:
from collections import Counter
class Solution:
def deleteAndEarn(self, nums: list[int]) -> int:
freqs = Counter(nums)
items = sorted(freqs.items())
prev2 = 0
prev1 = items[0][0] * items[0][1]
prev_x = items[0][0]
for x, freq in items[1:]:
points = x * freq
if x == prev_x + 1:
# Skip x: prev1
# Take x: prev2 + points
prev2, prev1 = prev1, max(prev1, prev2 + points)
else:
# No conflict, so taking x is always beneficial.
prev2, prev1 = prev1, prev1 + points
prev_x = x
return prev1
The states mean:
prev1: best score using all values up to the previous distinct value.prev2: best score using all values up to the distinct value before that.
Importantly, "using values up to" does not mean the last value was selected.
For your failing input, the aggregated rewards are:
After processing 2:
That score considers 2, but skips it. Your code instead stores 2, because every update unconditionally adds the current reward.
After processing 4, the corrected states are:
When processing 5:
The key missing idea is that a DP state stores the best result for a prefix, not necessarily a result that selected the prefix’s last value.