Abstract / Summary

Find the number that appears most often right after a given key in an 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 60% (80k+ 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 implementation defines a method that, given a list of integers and a target value, returns the integer that most frequently appears immediately after the target within the list. The algorithm proceeds in two distinct phases: first it builds a frequency map of all successors of the target, then it scans that map to locate the most frequent successor. The code is concise, leverages Python’s standard library for clarity, and performs the required work in a single linear pass over the input data.

Data structures used

A defaultdict from the collections module is employed to store the count of each integer that follows the target. This choice eliminates the need for explicit existence checks before incrementing a count, allowing the code to update frequencies with a single statement.

follow = defaultdict(int)

Main loop that populates the frequency map

The core of the algorithm iterates over adjacent pairs of elements in the input list by zipping the list with a one-position offset version of itself. For each pair, the first element is examined; if it matches the target key, the second element’s count is increased in the follow dictionary.

for a, b in zip(nums, nums[1:]):
    if a == key:
        follow[b] += 1

This construction ensures that every occurrence of the target is examined exactly once, and the corresponding successor is recorded without the overhead of index arithmetic.

Determining the most frequent successor

After the frequency map is populated, the method selects the integer with the highest count. The variable result is initialized to None. The loop iterates over the keys of the follow dictionary, updating result whenever a key with a larger count is found. The conditional expression also handles the initial assignment when result is still None.

result = None
for f in follow:
    if not result or follow[f] > follow[result]:
        result = f
return result

Because the loop examines each entry exactly once, the selection process is straightforward and avoids any sorting or additional data structures.

Edge cases handled by the implementation

When the input list contains fewer than two elements, the zip call yields no pairs, leaving the follow dictionary empty. Consequently, the final loop over follow does not execute, and the method returns None. This behavior gracefully handles an empty list or a list with a single element.

If the target key never appears in the list, the condition a == key is never satisfied, and again the follow dictionary remains empty. The method consequently returns None, indicating that there is no successor to report.

In situations where multiple successors share the same highest frequency, the selection loop retains the first encountered key with that maximal count because the comparison uses a strict greater-than operator. Thus the method deterministically returns the earliest such successor in the iteration order of the dictionary.

Performance optimizations observed

The algorithm benefits from several implicit optimizations. Using zip(nums, nums[1:]) creates an iterator that yields adjacent pairs without constructing an intermediate list, which conserves memory and reduces overhead. The defaultdict eliminates conditional branches that would otherwise be required to initialize counts, allowing each increment to be performed in constant time.

The two-phase approach-first building the frequency map, then scanning it-avoids nested loops and ensures that the total work scales linearly with the length of the input list. By not sorting the frequency map or employing additional data structures, the method minimizes both computational and memory footprints while still delivering the correct result.

Imagine you have a long row of colorful building blocks. Each block has a number written on it. The task is to look for a special number called the key. Every time you find the key block, you look at the block that comes right after it and keep a secret tally of which numbers follow the key the most.

You start by looking at every pair of blocks that are side by side. If the first block matches the special key, you put a checkmark next to the second block. You keep doing this until you have checked all the pairs in your row.

Once you have finished checking, you look at your tally to see which number has the most checkmarks. You pick that winner and hold it up high to show that it is the one that appears most often right after the key.

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

Time: linear
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++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		JS	Go		PHP	TS
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	fartem				Ruby
	fsq	C++
	JoshCrozier					JS
	lkwq007		Python
	muhammadfarhankt						Go
	suxrobGM							C#
	trung-hn		Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, PHP, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
trung-hn	Python
varunu28	Java

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