Abstract / Summary

Find the id that appears most often in a list of ids.

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 43% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Heap (Priority Queue)
• Ordered Set

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 defines a generator method that yields the most frequent identifier after each insertion. It processes two parallel input sequences: one containing identifiers and the other containing associated frequencies. The algorithm maintains a max-heap to keep track of the identifier with the highest cumulative frequency while using a dictionary to store the current totals for each identifier. By yielding the top of the heap after each update, the method produces a running view of the most frequent identifier.

Core Workflow

Initialization

high = []                         # max-heap (implemented with negated values)
have = defaultdict(int)          # maps each identifier to its cumulative frequency

The heap high will store pairs of the form (cumulative_frequency, identifier). Because Python’s heapq module implements a min-heap, frequencies are stored as their negative to achieve max-heap behavior. The dictionary have provides O(1) access to the current total for any identifier.

Processing Each Pair

for n, f in zip(nums, freq):
    f = -f                        # invert to work with a max-heap
    have[n] += f                  # update cumulative frequency for identifier n
    heappush(high, (have[n], n))  # push the new state onto the heap

For every identifier n and its associated frequency f, the code negates f, adds it to the running total in have, and pushes the updated pair onto the heap. This step ensures that the heap always contains the most recent cumulative frequency for each identifier that has been processed so far.

Lazy Removal of Stale Entries

while high:
    count, id = high[0]
    if count == have[id]:
        break
    heappop(high)

Because the heap may contain outdated entries (previous cumulative frequencies for the same identifier), the algorithm performs a lazy cleanup. It repeatedly examines the element at the top of the heap; if the stored count does not match the current value in have, the entry is discarded with heappop. This loop stops as soon as the top element reflects the latest cumulative frequency, guaranteeing that the heap’s root is always valid.

Producing the Result

yield -high[0][0]                 # invert back to the original frequency sign

After the heap has been cleaned, the method yields the negated count from the heap’s root, converting it back to a positive frequency. Since the method is a generator, callers receive a sequence of most-frequent frequencies corresponding to each incremental update.

Edge Cases Handled

When the input lists are empty, the zip iterator produces no elements, and the generator yields nothing, which is a natural and safe outcome. Duplicate identifiers are correctly aggregated because each occurrence updates the same entry in have; the heap receives a new tuple for the updated total, and stale tuples are removed lazily, ensuring the most recent total is used. The use of negated frequencies allows the algorithm to handle both positive and negative original frequencies without additional branching; the sign inversion is applied uniformly. If an identifier appears with a frequency of zero, the cumulative total remains unchanged, and the heap still receives a tuple reflecting the unchanged value; the lazy removal step will discard any redundant entry, leaving the heap’s top unchanged.

Performance Optimizations

The design leverages a dictionary for constant-time updates of cumulative frequencies, avoiding the need to scan a list of identifiers. By storing only the most recent cumulative value in the dictionary and pushing every update onto the heap, the algorithm sidesteps the overhead of locating and updating an existing heap entry. The lazy deletion loop removes stale entries only when they surface at the heap’s root, which amortizes the cost of cleanup across operations and prevents frequent re-heapification. Using negated frequencies to simulate a max-heap eliminates the need for a custom heap implementation, allowing the solution to rely on the highly optimized heapq module. The generator pattern yields results on demand, which can reduce memory pressure when the consumer processes the output incrementally.

Imagine that there is a big box full of labeled toys. Each toy has a specific number on it, and this code helps keep track of which number appears the most often in the box.

First, there is a special tool called a heap that acts like a busy librarian. This librarian is very good at finding the largest number, but because it is a bit tricky, the code uses negative numbers to help the librarian stay organized. Think of it like looking at things through a mirror where everything is flipped around.

The code goes through the list of toys one by one. Each time a toy with a certain number is added or taken away, it updates the total count for that number in a notebook. After updating the count, it tells the librarian to check the heap. The librarian looks at the top of the heap to see if the information there is still true and current. If the information is old or wrong because the counts changed, the librarian throws that old note away.

Once the librarian finds the most current and largest count at the top, the code flips that negative number back to a positive one so it makes sense again. It keeps doing this for every toy added to the pile, always making sure the answer reflects the current winner.

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

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