Abstract / Summary

Given an array with numbers from one to n and one duplicate find the repeated value.

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 65% (4+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Bit Manipulation
• 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 provided implementation solves the classic “find the duplicate number” problem by scanning the input array once while maintaining a hash-based container that records every value seen so far. As soon as a value is encountered that already exists in the container, the function returns that value as the duplicate. If the scan finishes without finding a repeat, the function returns -1.

Key Steps

Allocation of the hash container

The algorithm begins by creating an unordered_set<int> named has. Immediately after construction the code calls has.reserve(11000);. This call pre-allocates bucket space for roughly eleven thousand elements, which reduces the number of internal rehash operations when the set grows. The reservation is performed before any elements are inserted, ensuring that the container can accommodate a typical input size without costly expansions.

unordered_set<int> has;
has.reserve(11000);

Linear traversal of the input

The core of the solution is a range-based for loop that iterates over each integer n in the supplied vector nums. The loop processes elements in the order they appear, preserving the original sequence.

for (auto n : nums)
{
    // body omitted for brevity
}

Duplicate detection

Inside the loop the code checks whether the current element n is already present in the set by invoking has.count(n). The count method returns the number of occurrences of n in the set, which is either 0 or 1 because a set cannot hold duplicates. If the result is greater than zero, the function immediately returns n, signalling that a duplicate has been found.

if (has.count(n) > 0)
    return n;

Insertion of new elements

When the current element is not yet in the set, the algorithm inserts it using has.insert(n);. This operation adds the element to the hash table, making it available for future duplicate checks.

has.insert(n);

Fallback return

If the loop completes without triggering the early return, the function reaches the final statement return -1;. This return value indicates that no duplicate was detected during the scan, which can happen when the input does not satisfy the problem’s guarantee of at least one repeated element.

return -1;

Edge Cases Handled

The implementation gracefully handles an empty vector because the loop body is never executed, and the function proceeds directly to the fallback return of -1. When the duplicate appears as the very first element examined, the has.count check fails for the initial occurrence, the element is inserted, and the subsequent identical element triggers the immediate return. If the duplicate resides at the end of the array, the algorithm continues inserting each distinct value until the final element matches one already stored, at which point it returns the duplicate. The use of an unordered_set<int> also accommodates the full range of signed 32-bit integers, so both positive and negative values are processed without special handling.

Performance Optimizations

The explicit reservation of bucket space (has.reserve(11000)) is a notable optimization. By allocating sufficient capacity up front, the code avoids repeated rehashing and memory allocation that would otherwise occur as the set grows during insertion. This pre-allocation improves cache locality and reduces the overhead associated with dynamic resizing.

The choice of unordered_set provides average-case constant-time operations for both the membership test (count) and the insertion (insert). Because the algorithm performs exactly one membership test and, when necessary, one insertion per element, the overall work done per element remains minimal.

Early termination is another performance benefit. As soon as a duplicate is discovered, the function exits, preventing any further unnecessary processing of the remaining elements. This behavior is especially advantageous for inputs where the duplicate appears early in the sequence.

Overall, the combination of pre-allocation, hash-based constant-time operations, and early exit yields a solution that processes the input efficiently while using a straightforward and readable approach.

Imagine a big basket full of numbered blocks. Some of the numbers might be exactly the same, and the goal is to find the one that shows up twice. To do this, think of a notebook where every page is empty at the start.

The code walks through the pile of blocks one by one. It picks up a block and looks at the number written on it. Then, it flips to the page in the notebook that matches that number. If the page is already filled with a little mark, it means that number was seen once before, which reveals that this specific block is the extra one being searched for.

If the page inside the notebook is still blank, it makes a little mark on it so that the notebook remembers seeing that number. It keeps checking every block in the pile until it spots the one that already has a mark waiting for it. Once that sneaky duplicate is found, the work is finished.

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++	Java			Python					TS
	WalkCCC	C++	Java			Python
	leetcode.ca	C++	Java		Rust	Python	JS	Go			TS
	LeetcodeHelp	C++	Java			Python
	MemoryLimitExceeded	C++				Python
	Progiez	C++	Java			Python
github	aylei				Rust
	BigEggStudy			C#
	black-shadows	C++
	bujosa				Rust
	charles-wangkai		Java
	chenyanzhe	C++
	Dijkstra-Edu		Java
	everthis						JS
	fartem								Ruby
	FelixFan1122			C#
	fpdjsns	C++
	Garvit244					Python
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007					Python
	MacJim	C++
	muhammadfarhankt							Go
	pruthvikp					Python
	ruoru				Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28		Java
	vli02									C
	vthwang		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
muhammadfarhankt	Go
pruthvikp	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
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