Abstract / Summary

You must remove targets in sequence starting from the first available each time until none remain.

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 42% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• 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 Solution class implements a method destroyTargets that receives a list of integers nums and an integer space. The goal is to identify a value from nums that, when used as a starting point, can “destroy” the maximum number of targets under the rule that all numbers sharing the same remainder when divided by space belong to the same destruction line. If several remainders achieve the same maximal count, the smallest original number among those lines is returned.

Core Logic

Building remainder statistics

modulo = defaultdict(int)   # counts per remainder
low    = defaultdict(int)   # smallest number per remainder
for n in sorted(nums):
    remainder = n % space
    modulo[remainder] += 1
    if remainder not in low:
        low[remainder] = n

The loop iterates over the sorted input list. For each element n, the remainder n % space is computed. The modulo dictionary accumulates how many numbers belong to each remainder class. Simultaneously, the low dictionary records the smallest number observed for each remainder. Because the list is processed in ascending order, the first occurrence of a remainder is automatically the smallest value for that class, and the conditional guard if remainder not in low guarantees that later larger numbers do not overwrite the stored minimum.

Determining the optimal remainder

most = max(modulo.values())
candidates = [low[key] for key, value in modulo.items() if value == most]
return min(candidates)

After the counting phase, most holds the highest frequency among all remainder groups. The comprehension extracts the smallest original number (low[key]) for each remainder whose count equals most. Finally, the smallest of those candidates is returned, satisfying the tie-breaking rule.

Edge Cases Handled

When nums contains only one element, the loop still populates both dictionaries with a single entry, most becomes 1, and the single candidate is returned correctly.

If space is larger than any element in nums, each number yields a distinct remainder equal to the number itself. The algorithm then treats every number as its own line, and the smallest number is chosen because all counts are equal to 1.

When multiple numbers share the same remainder, the sorted traversal ensures that low captures the minimal number for that remainder, even if the list includes duplicate values. The counting mechanism correctly aggregates duplicates, so the maximal count reflects the true size of the line.

If space equals 1, every number maps to remainder 0, resulting in a single entry in modulo with a count equal to the length of nums. The low entry for remainder 0 becomes the smallest number in the entire list, which is then returned.

Performance Optimizations

The algorithm sorts nums once, which orders the data and simultaneously enables the low dictionary to be filled without additional comparisons. By checking if remainder not in low instead of updating with min, the code avoids unnecessary function calls and conditional evaluations for already-seen remainders.

Using defaultdict(int) for modulo eliminates the need for explicit existence checks before incrementing counts, streamlining the counting loop.

The final selection of candidates leverages a dictionary comprehension that iterates over modulo.items() only once, extracting the relevant minima directly from low. This avoids a second pass over the original list.

Overall, the method runs in O(N log N) time due to the initial sort, with all subsequent operations executing in linear time relative to the number of distinct remainders, and it uses O(R) auxiliary space where R is the number of unique remainders.

Imagine you have a big bucket full of numbered building blocks. You want to group them together using a special magic trick. This magic trick uses a number called space. When you take a block and divide it by that space number, the bit that is leftover is called a remainder. Every block that has the same remainder can be put into the same pile.

The code starts by looking at every block one by one. It figures out the remainder for each block and puts it in the right pile. It also keeps track of how many blocks are in each pile and remembers which block was the smallest one in that group.

After all the blocks are sorted into piles, the code looks for the pile that has the most blocks in it. Sometimes there might be a tie where two different piles both have the maximum number of blocks. If that happens, the code looks at the smallest block in each of those winning piles. Finally, it picks the smallest number among those winners to finish the game.

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

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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++	Java		Python	TS
	WalkCCC		C++	Java		Python
	leetcode.ca		C++	Java	Go	Python
	Progiez		C++	Java		Python
github	charles-wangkai			Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
wisdompeak	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