Community Problem

Delete and Earn

Difficulty: Medium

Maximize total points earned by picking values, where picking value v deletes v-1 and v+1, by reducing to House Robber on a frequency line.

Delete and Earn

Maximize total points earned by picking values, where picking value v deletes v-1 and v+1, by reducing to House Robber on a frequency line.

MEDIUM

Free

dynamic-programming

arrays

hash-table

By CodeSnatch

December 19, 2025

Updated May 20, 2026

262 views

4.5 (9)

I had this on a Snowflake systems-onsite and the moment I sketched a frequency array, my interviewer just said "yes, that's House Robber." The reduction is the whole problem: aggregate by VALUE (not by index), then run House Robber on the value-line where each cell v carries weight v * count[v]. The catalog covered house-robber, but it skipped this counting variant where the input is unsorted and values repeat.

Delete and Earn

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

Pick any nums[i] and delete it to earn nums[i] points. After this, you must delete EVERY element equal to nums[i] - 1 and EVERY element equal to nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

Examples

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: Pick 4 (earn 4, delete the 3 and 5s; the 2 stays), then pick 2 (earn 2). Total 4 + 2 = 6.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: Pick all three 3s (earn 9; the 2s and 4s are deleted as side effects). 9 > 2 * 2 + 4 = 8.

Example 3:

Input: nums = [1]
Output: 1
Explanation: Pick the only element.

Example 4:

Input: nums = [1, 1, 1, 2, 4, 5, 5, 5, 6]
Output: 18
Explanation: Pick all 1s (3) skip 2, then choose 5s (15). Total 3 + 15 = 18.

Constraints

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

Follow-up

Why does aggregating by value reduce this to House Robber? Once you decide to take ANY copy of value v, you might as well take ALL copies (the deletion side effects are the same). So the decision is per-value, not per-index. The constraint "taking v forbids taking v - 1 and v + 1" is exactly the no-adjacent-houses rule of House Robber on a frequency-weighted line indexed by value.

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach: Reduce to House Robber on the Value Line (O(n + maxV) time, O(maxV) space)

Observe two facts:

Picking any one copy of value v deletes ALL copies of v - 1 and v + 1. So once you commit to v, you should take every copy of v; partial commitment is strictly worse.
The decision "take v or not" forbids taking v - 1 and v + 1. This is exactly the no-adjacent-houses constraint of House Robber, with the houses laid out on the integer line indexed by value, and the loot at house v equal to v * count(v).

Algorithm

Find maxV = max(nums) in O(n).
Build points[0..maxV] where points[v] = v * count(v). (Use points[v] += nums[i] while walking nums.)
Run House Robber over points. With prev = best for [0..v-2] and curr = best for [0..v-1], the recurrence at v is next = max(prev + points[v], curr). Slide forward.
Return curr after the loop.

Why It Works

Step 1 collapses the multi-copy structure into a per-value points array. Step 2 is exactly House Robber (proven optimal by the classic DP argument: at each house you either take and advance two steps, or skip and advance one). The optimality of House Robber transfers verbatim to the reduction.

Complexity

Space + time

Text

Time    O(n + maxV)
Space   O(maxV) for points; O(1) extra for the rolling prev/curr

With maxV <= 10^4 and n <= 2 * 10^4, both are tiny.

Pitfalls

Sorting unique values and running House Robber on the sorted-unique sequence. This is WRONG when the unique values have gaps: [2, 4] is not adjacent (no 3), so you can take both, but a sorted-unique House Robber would treat them as adjacent. The points-array approach handles gaps correctly because the gap cells have points[v] = 0, and House Robber over a 0 cell trivially picks both neighbors.
Forgetting points[v] += nums[i] should accumulate, not set. Each occurrence adds v to the bucket; points[v] = nums[i] would only count once.
Allocating points of size n instead of maxV + 1. The index is the VALUE, not the position. Mis-sizing produces out-of-bounds for the largest value or wastes memory.

Solution Code

All Problems