← DSA Atlas
Dedicated problem page · #740

Delete and Earn

MediumOne-Dimensional Dynamic ProgrammingReduce to House Robber over value buckets1-D DP (take / skip on consecutive values)
Solve on LeetCode ↗
740
MediumOne-Dimensional Dynamic Programming1-D DP (take / skip on consecutive values)Reduce to House Robber over value buckets

Delete and Earn

Given an integer array nums, repeatedly pick any element nums[i], earn nums[i] points, and then delete every element equal to nums[i] - 1 and nums[i] + 1 (all copies). Return the maximum total points you can earn.

Open official problem prompt ↗
In plain English

Find the maximum score achievable when earning a value's points bans you from ever earning the values one above and one below it.

Picture it like this

Like harvesting crops in numbered rows where cutting any plant in row v triggers a herbicide that kills rows v-1 and v+1: you never lose by taking every plant in a chosen row, so you plan which non-adjacent rows to keep.

Example
Input
nums = [3, 4, 2]
Output
6
Why
Take 4 (earn 4, which forces deleting all 3s), then take 2 (earn 2); 4 + 2 = 6.
Constraints
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^4
Pattern lesson

See the pattern, then code

Reduce to House Robber over value buckets
Recognition clue

Choosing a value forbids the adjacent values (v-1 and v+1), and picking one copy of v means you may as well pick them all. That 'pick a value, lose its neighbors' rule over the number line is exactly House Robber on consecutive integers.

↗
One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Collapse duplicates: define points[v] = v * (count of v). Since taking any copy of v deletes all of v-1 and v+1 anyway, the decision is per-value, not per-element. Now it is House Robber where 'adjacent houses' are consecutive integers v-1 and v.

New words, made simpleKnow these before the algorithm
Value bucket
Total points obtainable from a single value v, equal to v times how many times it appears.
Take / skip
Two running DP values: the best total that ends by earning the current value, versus the best that ignores it.
Adjacency constraint
Earning value v forbids earning v-1 and v+1, mirroring House Robber's no-two-adjacent rule.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force subset search

Exponential in the value range; impossible for m up to 10^4.

Try every subset of distinct values that has no two consecutive integers and score it.

Time O(2^m)Space O(m)
Best choiceHouse Robber DP on value buckets

Linear and exact; the standard accepted solution.

Aggregate points per value, then run the linear take/skip recurrence across consecutive integers.

Time O(n + m)Space O(m)
The rule we keep true

Invariant

After processing value v, take = the maximum points using values <= v with v earned, and skip = the maximum points using values <= v with v not earned.

Why this is correct

Reasoning

Because earning any copy of v deletes all copies of v-1 and v+1 regardless, taking a value is all-or-nothing and only conflicts with its two integer neighbors. That makes the problem identical to House Robber over the integer line, where the take/skip recurrence provably maximizes a no-adjacent selection.

The algorithm in three movesSay these aloud before coding
1Bucket the input: points[v] = v times its frequency, indexed by value up to max(nums)

points = [0,0,2,3,4]

2Sweep values 1..max, maintaining take (best if you earn current value) and skip (best if you don't)

v=3: take=3, skip=2

3take_new = skip + points[v]; skip_new = max(take, skip)

v=4: take=2+4=6, skip=3 -> ans 6

4Return max(take, skip) after the last value

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
v=1:00
v=2:21
v=3:32
v=4:43
1 · Readnums = [3,4,2]
2 · AskHow many points does each value give?
3 · Update statepoints = [0,0,2,3,4]
4 · ResultValue 2->2, 3->3, 4->4.
Key takeaway

Points bucketed by value; taking v=4 (skip v=3) plus v=2 yields the max 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Bucket points by value

    points[v] accumulates v for every occurrence, folding duplicates and the point calculation into one array indexed by value.

  2. 2
    Lines 7-9Linear take/skip sweep

    Iterate values 1..max; take becomes skip+points[v] (earn v, so previous value was skipped) and skip becomes max(take, skip).

  3. 3
    Lines 10Answer

    The optimum may or may not earn the largest value, so return max(take, skip).

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element -> earn it and return that value
  • All identical values (e.g. [2,2,2]) -> earn every copy since there is no neighbor to lose
  • Values with gaps (e.g. [1,1,1,100]) -> non-adjacent, so earn both groups
  • Large duplicate counts where v * count dominates
!

Common beginner mistakes

  • Running House Robber on the raw array order instead of on sorted/bucketed values
  • Forgetting to multiply value by its frequency (using count instead of total points)
  • Sizing the points array to len(nums) rather than max(nums)+1
  • Treating equal values as adjacent conflicts when only v-1 and v+1 conflict
Check your understanding

Why is it safe to always take every copy of a chosen value rather than just one copy?

More in One-Dimensional Dynamic Programming

#198House RobberTake-or-skip linear DP#322Coin ChangeUnbounded knapsack (min coins)#300Longest Increasing SubsequencePatience sorting (tails array)#5Longest Palindromic SubstringExpand around center#32Longest Valid ParenthesesIndex stack with sentinel base#70Climbing StairsFibonacci-style linear DP