How do you approach Delete and Earn?

Bucket total points by value, then it becomes House Robber over values.

What are common mistakes on Delete and Earn?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Delete and Earn

MediumAlgorithms

Description

You are given an integer array `nums`. In one operation you pick a value, earn that many points, and then must delete **every** element equal to `value - 1` and `value + 1`. Return the maximum number of points you can earn.

Example 1

Input: nums = [3,4,2]

Output: 6

Explanation: Take 4 (delete 3s), then take 2 -> 4 + 2 = 6.

Example 2

Input: nums = [2,2,3,3,3,4]

Output: 9

Explanation: Take all 3s (9), deleting 2s and 4s.

Constraints

- 1 <= nums.length <= 2 * 10^4 - 1 <= nums[i] <= 10^4

Delete and Earn: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 4 test cases (2 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 2-step hint ladder

Bucket total points by value, then it becomes House Robber over values.
You can't take adjacent values, so dp[v] = max(skip, take v plus dp[v-2]).

The optimal approach

Show the approach: The approach

House Robber on value buckets. Sum points for each value into `points[v]`. Taking `v` forbids `v-1` and `v+1`, so this is the House Robber recurrence over the value axis: `cur = max(cur, prev + points[v])`.

Time: O(n + maxVal). Space: O(maxVal).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.