Abstract / Summary

You can delete numbers to earn points and want to maximize total points by choosing which to delete without taking adjacent values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (800k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “Delete and Earn” problem by transforming it into a dynamic-programming recurrence over distinct numeric values. It first builds a frequency map of the input numbers, then extracts the sorted unique values. The core of the algorithm is a memoized recursive function deeper that decides, for a given starting value, whether to take the current value (and consequently skip the next integer) or to skip it and consider the following value. The recursion terminates when the search index reaches the end of the sorted list. The final answer is obtained by invoking deeper with a starting value of zero.

Construction of Frequency Map

The method deleteAndEarn begins by populating a dictionary that records how many times each integer appears in the input list. The loop iterates over the sorted input, ensuring that the keys are inserted in ascending order, which later enables binary search on the keys.

self.freq = defaultdict(int)
for n in sorted(nums):
    self.freq[n] += 1
self.values = list(self.freq.keys())

By using defaultdict(int), missing keys default to zero, simplifying the accumulation logic. The sorted iteration guarantees that self.values is already ordered, a prerequisite for the binary-search operations that follow.

Recursive Decision Function

The heart of the solution is the deeper method, decorated with @cache to memoize results for each distinct value argument. Memoization eliminates repeated work for overlapping sub-problems, turning the exponential recursion into a linear-time process over the distinct values.

@cache
def deeper(self, value):
    a = bisect_left(self.values, value)
    if a == len(self.values):
        return 0

    one    = self.values[a]
    sumOne = one * self.freq[one] + self.deeper(one + 2)

    b = bisect_left(self.values, value + 1, a + 1)
    if b == len(self.values):
        return sumOne

    two    = self.values[b]
    sumTwo = two * self.freq[two] + self.deeper(two + 2)
    return max(sumOne, sumTwo)

Search for the First Viable Value

The call to bisect_left(self.values, value) finds the index of the smallest element that is not less than value. If the index equals the length of self.values, the recursion has exhausted all candidates and returns zero. This condition gracefully handles the edge case where the input list is empty or when the recursion has moved beyond the largest number.

Option 1 - Take the Current Value

When a viable element one is found, the algorithm computes the total points earned by taking all occurrences of one. This is expressed as one * self.freq[one]. Because taking one eliminates one-1 and one+1 from future consideration, the next recursive call advances to one + 2. The result of this branch is stored in sumOne.

Search for the Next Distinct Value

The second binary search, bisect_left(self.values, value + 1, a + 1), looks for the smallest element that is at least one greater than the current value. Starting the search from a + 1 skips the element already examined, ensuring that the algorithm does not revisit the same number. If this search reaches the end of the list, the function returns sumOne, meaning that only the first option is available.

Option 2 - Skip to the Next Distinct Value

When a second viable element two exists, the algorithm evaluates the alternative of taking two (and consequently skipping two-1 and two+1). The points contributed by this choice are two * self.freq[two], and the recursion proceeds to two + 2. The total for this branch is stored in sumTwo. The final return value of deeper is the maximum of sumOne and sumTwo, reflecting the optimal decision at the current stage.

Edge Cases Handled

The recursion’s base condition (a == len(self.values)) naturally returns zero for an empty input list, ensuring that deleteAndEarn yields a correct result of zero when no numbers are provided.

When all input numbers are identical, the frequency map contains a single key. The first binary search finds this key, and the second search immediately reaches the end of the list, causing the function to return the product of the value and its frequency, which is the optimal outcome.

If the input contains large gaps between numbers (for example, [1, 1000]), the binary searches efficiently skip over missing integers, and the recursion correctly evaluates each isolated cluster without unnecessary iteration over absent values.

When the smallest number in the input is greater than zero, the initial call self.deeper(0) still works because bisect_left will locate the first existing value, and the algorithm proceeds from there without any special handling.

Performance Optimizations

The use of @cache on the recursive function eliminates redundant calculations for the same value argument, turning what would be an exponential exploration into a linear pass over the distinct numbers.

Binary search via bisect_left provides O(log n) lookup for the next candidate value, allowing the algorithm to jump directly to relevant positions in the sorted list rather than scanning sequentially.

Storing frequencies in a dictionary and pre-computing the list of unique sorted values reduces the overhead of counting occurrences during recursion.

By advancing the recursion to value + 2 after taking a number, the algorithm respects the problem’s constraint that adjacent numbers become unavailable, thereby pruning the search space early and avoiding unnecessary recursive branches.

Overall, the combination of memoization, binary search, and pre-processed frequency data yields an implementation that scales efficiently with the number of distinct input values.

Imagine having a big pile of number blocks on the floor. Each number block has a value, like a five or a ten, and each one might appear multiple times in the pile. When a number is picked to earn points, all the numbers that are one smaller and all the numbers that are one larger than it must disappear forever. The goal is to collect as many points as possible without losing the bigger blocks.

The computer starts by counting how many of each number exists and putting them in order from smallest to biggest. The code then looks at the first available number. It makes a choice between two paths. In the first path, the computer picks that number and collects all the points for every copy of it. Because that number was picked, the computer cannot use any numbers that are one value higher, so it cleverly skips ahead to look at numbers that are two steps bigger.

In the second path, the computer decides to skip that first number entirely and looks at the next available number instead. It sees how many points it could get by starting there and skipping ahead. After exploring both paths, the computer compares the two totals and keeps the one that gives the most points. It keeps doing this over and over until it reaches the end of the pile, remembering the results along the way so it does not have to do the same work twice. Eventually, this process reveals the highest score that can be earned from the entire pile.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java			TS
	WalkCCC	C++				Java
	leetcode.ca	C++	Python			Java		Go
	LeetcodeHelp	C++	Python			Java
	Progiez	C++	Python			Java
github	black-shadows	C++
	bujosa		Python
	charles-wangkai					Java
	everthis			JS
	fengvyi	C++
	fpdjsns	C++
	JoshCrozier			JS
	lkwq007		Python
	ruoru				Rust
	suxrobGM						C#
	trung-hn		Python
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality