AlgoMaster Logo

Delete and Earn

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

A greedy strategy, repeatedly taking the highest-value element, does not work here. Taking a number deletes every copy of its neighbors, and those neighbors can be worth more in total than the number you took.

Two observations reshape the problem. First, if you earn points from some value k, you should earn from all copies of k: taking one copy already deletes every k-1 and k+1, so the remaining copies of k cost nothing extra to take. Earning from k is therefore an all-or-nothing decision worth k * count(k) points. Second, that decision rules out k-1 and k+1 entirely. This take-or-skip structure, where taking a value forbids its neighbors, is the House Robber problem: there you cannot rob two adjacent houses, here you cannot earn from two adjacent values.

So the strategy is to aggregate the total points for each value (value * frequency), treat those totals as a row of houses, and apply the House Robber recurrence.

Key Constraints:

  • 1 <= nums.length <= 2 * 10^4 --> One linear pass aggregates the points per value. After that, the running time depends on the value range, not on n.
  • 1 <= nums[i] <= 10^4 --> Values are bounded, so an array indexed by value (size at most 10001) can replace a hash map. The maximum possible total is 2 10^4 elements 10^4 points each = 2 * 10^8, which fits in a 32-bit integer.

Approach 1: Recursion (Brute Force)

Intuition

First, aggregate the points for each value: if value k appears f times, taking k earns k * f points. Store these totals in a points array indexed by value. The question for each value is then binary: take it or skip it.

A recursive function expresses this decision directly. The best score over values 0 through i is either the best over 0 through i-1 (skip value i) or points[i] plus the best over 0 through i-2 (take value i, which forbids i-1).

Algorithm

  1. Find the maximum value maxVal in nums.
  2. Build an array points of size maxVal + 1, where points[k] = k * (number of times k appears in nums).
  3. Define a recursive function solve(i) that returns the max points from values 0 through i.
  4. Base cases: solve(0) = points[0], solve(1) = max(points[0], points[1]), negative indices return 0.
  5. Recursive case: solve(i) = max(solve(i - 1), points[i] + solve(i - 2)).
  6. Call solve(maxVal).

Example Walkthrough

1nums = [2, 2, 3, 3, 3, 4] -> points[k] = k * count(k)
0
0
1
0
2
4
3
9
4
4
1/7

Code

Approach 2: Memoization (Top-Down DP)

Intuition

The recursion in Approach 1 solves the same subproblems repeatedly. When computing solve(i), we call solve(i-1) and solve(i-2). But solve(i-1) also calls solve(i-2), so solve(i-2) is computed twice. The duplication compounds at every level, which is where the exponential running time comes from.

Memoization removes the repeated work: cache the result of each solve(i) call, and on every later call for the same i, return the cached value. Each subproblem is then solved once.

Algorithm

  1. Build the points array the same way as Approach 1.
  2. Create a memo array of size maxVal + 1, initialized to -1 (indicating "not computed").
  3. In the recursive function, check the memo before computing. After computing, store the result in memo.
  4. Call solve(maxVal).

Example Walkthrough

1nums = [2, 2, 3, 3, 3, 4] -> points = [0, 0, 4, 9, 4], memo = [-1, -1, -1, -1, -1]
0
0
1
0
2
4
3
9
4
4
1/8

Code

Approach 3: Tabulation (Bottom-Up DP)

Intuition

Instead of starting from the top and recursing down, we can flip the approach and build up from the bottom. We create a DP table where dp[i] represents the maximum points we can earn considering values from 0 through i. We fill this table left to right, and each entry depends only on the two previous entries.

The recurrence is the same as before:

  • dp[i] = max(dp[i-1], points[i] + dp[i-2])

Algorithm

  1. Build the points array (same as before).
  2. Create a dp array of size maxVal + 1.
  3. Set dp[0] = points[0] and dp[1] = max(points[0], points[1]).
  4. For each value i from 2 to maxVal, compute dp[i] = max(dp[i-1], points[i] + dp[i-2]).
  5. Return dp[maxVal].

Example Walkthrough

1nums = [2, 2, 3, 3, 3, 4] -> points = [0, 0, 4, 9, 4]. Initialize dp
0
0
1
0
2
0
3
0
4
0
1/7

Code

Approach 4: Space-Optimized DP

Intuition

Looking at the recurrence dp[i] = max(dp[i-1], points[i] + dp[i-2]), each computation only uses the two most recent values. We don't need to store the entire DP table. Instead, we can maintain two variables: prev2 (representing dp[i-2]) and prev1 (representing dp[i-1]). As we iterate, we update these variables in a rolling fashion.

This is the same optimization used in the classic Fibonacci problem: instead of storing all n Fibonacci numbers, you only need the last two.

Algorithm

  1. Build the points array (same as before).
  2. Initialize prev2 = points[0] and prev1 = max(points[0], points[1]).
  3. For each value i from 2 to maxVal:
    • Compute current = max(prev1, points[i] + prev2).
    • Update: prev2 = prev1, prev1 = current.
  4. Return prev1.

Example Walkthrough

1nums = [2, 2, 3, 3, 3, 4] -> points = [0, 0, 4, 9, 4]. prev2=0, prev1=0
0
prev2
0
1
0
prev1
2
4
3
9
4
4
1/5

Code

Every approach so far indexes an array by value, so the DP work and memory scale with the maximum value M even when nums contains only a few distinct numbers. For nums = [1, 10000], the points array holds 10001 entries to represent two values. The final approach removes the dependence on M.

Approach 5: Sorted Distinct Values (Sparse DP)

Intuition

The dense points array serves two purposes: it puts the values in increasing order, and it makes adjacent values sit next to each other. A hash map of gains plus a sorted list of the distinct values provides the same information without materializing the empty slots.

Iterate over the distinct values in increasing order, carrying the same two rolling variables as Approach 4, where prev1 is the best total over all values processed so far and prev2 is the best total excluding the most recent one. Two cases arise at each value v with gain g:

  • v is exactly one more than the previous distinct value: the House Robber conflict applies, so current = max(prev1, prev2 + g). Using prev2 here is safe because the distinct value two positions back is at most v - 2, which never conflicts with v.
  • There is a gap before v: it conflicts with nothing already processed, and since every gain is positive (values and counts are at least 1), skipping it can never improve the total. Take it unconditionally: current = prev1 + g.

Algorithm

  1. Build a hash map gain where gain[v] = v * count(v).
  2. Extract the distinct values and sort them in ascending order.
  3. Initialize prev2 = 0, prev1 = 0, and prevVal = -1 (no value conflicts with -1, since all values are at least 1).
  4. For each value v in sorted order, with g = gain[v]:
    • If v == prevVal + 1, set current = max(prev1, prev2 + g).
    • Otherwise, set current = prev1 + g.
    • Shift the variables: prev2 = prev1, prev1 = current, prevVal = v.
  5. Return prev1.

Example Walkthrough

1nums = [1, 2, 2, 9, 9, 3, 3] -> sorted distinct values [1, 2, 3, 9], gains [1, 4, 6, 18]
0
1
1
2
2
3
3
9
1/6

Code

Within this problem's constraints (values at most 10^4), Approaches 4 and 5 perform comparably. The sparse version is the one that keeps working when the values range up to 10^9, where a dense array indexed by value is no longer an option.