What is the brute force approach and complexity for Delete and Earn?

Group the values and recurse over them in order: take or skip, and no taking v right after v − 1 with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Delete and Earn?

Store points[v] = v × count(v) in an array indexed by value, then run House Robber over it with optimal time complexity O(N + M) and space complexity O(M).

How do you identify the pattern for Delete and Earn?

Look for key signals in the prompt: "delete x − 1 and x + 1" indicates Neighbours are numbers next to each other in value, not in the array. That is a House Robber on the values.; "every copy of x earns points, copies are not deleted" indicates The points for a value add up, so each value is worth v × count. That gives the bucket.; "the most points" indicates At each value keep the better of two options: skip it, or take it and drop its neighbours..

Delete and Earn

Medium·LeetCode #740 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You have a list of whole numbers. You may repeat this move as many times as you like: pick any number x in the list, delete it, and earn x points. Then you must also delete every number equal to x − 1 and every number equal to x + 1.

Copies of x are not deleted by the move, so you can pick them one by one. Return the most points you can earn.

Input

nums, a list of whole numbers. Repeats are allowed.

Output

The largest number of points you can earn.

Example 1

Input: nums = [3, 4, 2]

Output: 6

Pick 4 to earn 4. That deletes the 3 (4 − 1). The 2 is still there, so pick it to earn 2. Total 6.

Example 2

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

Output: 9

Pick a 3 three times. Each pick earns 3, so that is 9. The first pick deletes the 2s and 4s, but the other 3s stay, so all three can be picked.

Example 3

Input: nums = [1, 1, 5]

Output: 7

Values 1 and 5 are not next to each other, so both can be used: 1 + 1 + 5 = 7.

Constraints

• 1 ≤ nums.length ≤ 2 × 10^4
• 1 ≤ nums[i] ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“delete x − 1 and x + 1”

→ Neighbours are numbers next to each other in value, not in the array. That is a House Robber on the values.

“every copy of x earns points, copies are not deleted”

→ The points for a value add up, so each value is worth v × count. That gives the bucket.

“the most points”

→ At each value keep the better of two options: skip it, or take it and drop its neighbours.

Approach Complexity Ladder

Brute Force — take or skip each distinct value, in orderO(2^N)O(N)

Group the values and recurse over them in order: take or skip, and no taking v right after v − 1

Better — sort, group, then dp over the distinct valuesO(N log N)O(N)

Sort and group, then run a dp; a value clashes with the previous one only when it is exactly one more

Optimal — bucket by value, then two variablesO(N + M)O(M)

Store points[v] = v × count(v) in an array indexed by value, then run House Robber over it

Brute Force Intuition

Group the numbers by value, so each distinct value v is worth v × count. Walk the distinct values from smallest to largest. For each one, either take it, which is blocked when the value just below it was taken, or skip it. Keep the larger total.

Recognition rule for this sub-pattern:

At each element: take it (and skip neighbours) or skip it. dp[i] = max(skip, take).

Remember this · DP — 1D Linear

Trigger

"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.

Think

If I knew the answer for every smaller prefix, how would I get the answer for i?

Key question

What does dp[i] mean in one sentence?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — 1D Linear translate into production architectures and low-level memory mechanics.

LLD Architecture