Abstract / Summary

Given an array of integers, repeatedly remove pairs of equal elements until no more pairs exist and find the smallest possible length of the array.

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 28% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Counting
• Greedy
• Hash Table
• Two Pointers

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 minLengthAfterRemovals method receives a list of integers and determines the smallest possible size of the list after repeatedly removing two elements that have different values. The algorithm works by focusing on the frequencies of each distinct number, using a max-heap to always pair the most abundant values first, and stops when no further valid pairs can be formed.

Key Steps

Frequency Counting

The method first builds a frequency map that records how many times each integer appears in the input list.

freq = defaultdict(int)
for n in nums:
    freq[n] += 1

Building a Max-Heap

To efficiently retrieve the most frequent values, the frequencies are negated and placed into a heap, turning Python’s min-heap into a max-heap.

todo = [ -v for v in freq.values() ]
heapify(todo)
print(todo)

Early Termination When a Dominant Value Exists

If the count of the most frequent number (high) exceeds the total count of all other numbers (other), the algorithm can immediately compute the remaining length, because the dominant value cannot be paired with itself.

high  = -todo[0]
other = size - high
if high > other:
    return high - other

Pairing Process Using Heap Operations

When a dominant value does not exist, the method repeatedly extracts the two largest frequencies, reduces each by one (representing the removal of a pair of distinct numbers), and updates the heap accordingly. The use of heapreplace avoids an extra pop-push cycle, and elements that reach zero are omitted from the heap.

while len(todo) >= 2:
    one = heappop(todo) + 1          # decrement most frequent
    two = todo[0] + 1                # peek second most frequent and decrement
    if two != 0:
        heapreplace(todo, two)      # replace top with updated value
    else:
        heappop(todo)                # remove zero-frequency entry

    if one != 0:
        heappush(todo, one)          # reinsert if still positive

Final Result Determination

After the loop finishes, the heap contains at most one element. Its length (0 or 1) directly represents the minimal possible size of the list.

return len(todo)   # 0 or 1

Edge Cases Handled

The algorithm explicitly addresses the situation where a single value dominates the list. In that case, the early return computes the exact leftover count without entering the pairing loop. The loop condition len(todo) >= 2 naturally stops when fewer than two distinct values remain, covering scenarios where the list becomes empty or contains only one distinct element after successive removals. Zero-frequency entries are removed promptly, ensuring they do not interfere with further pairing decisions.

Performance Optimizations

Negating frequencies to repurpose the built-in min-heap as a max-heap eliminates the need for a custom comparator and keeps heap operations fast. The choice of heapreplace over a separate heappop followed by heappush reduces the number of heap adjustments per iteration, cutting down overhead. By checking for zero after each decrement and discarding such entries immediately, the heap size stays as small as possible, which speeds up subsequent heappop and heapreplace calls. The early exit when a dominant frequency is detected prevents unnecessary processing of the entire heap in cases where the answer can be derived instantly.

Imagine a big pile of colored blocks sitting on the floor. Some blocks have the same color, and the goal is to take them away by grabbing two at a time. The trick is that you are not allowed to pick up two blocks if they are the exact same color.

The code starts by counting how many blocks of each color there are. It looks for the color that has the most blocks, because that group is the hardest to clear away. If one color has so many blocks that they take up more than half of the whole pile, those extra blocks will definitely be left over at the end. It is impossible to pair them all up without matching two of the same color, so they just stay on the floor.

If there are not too many of one color, the code starts a game of pairing. It takes the two colors that have the most blocks left and removes one from each. By always picking the biggest groups to shrink, the pile gets smaller and smaller. It keeps doing this, always picking the largest groups to pair off, until there are almost no blocks left. If the total number of blocks was even, the floor might end up completely empty. If it was odd, there might be just one lonely block sitting there at the finish.

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