Abstract / Summary

Given an array of numbers from one to n with some missing, list all the numbers that are not present in 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 64% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• 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 solves the problem of identifying all integers in the range 1 to n that are absent from the input list nums, where n equals the length of nums. The algorithm follows a straightforward two-phase approach: first it constructs a hash-based collection of the values present in the input, then it scans the complete numeric range and records any value that does not appear in the collection. The result is returned as a list of the missing numbers.

Core Logic

The first significant operation creates a set from the input list. This conversion collapses duplicate entries and enables constant-time membership checks.

all = set(nums)

Next, an empty list is prepared to accumulate the missing numbers.

result = []

The algorithm then iterates over the inclusive range from 1 to len(nums). For each candidate value it performs a membership test against the previously built set. When the candidate is not found, it is appended to the result list.

for i in range(1, len(nums) + 1):
    if i not in all:
        result.append(i)

Finally, the populated list of missing integers is returned.

return result

Edge Cases

The code gracefully handles an empty input list. In that scenario len(nums) is zero, the range generated for the loop is empty, and the function returns an empty list, correctly indicating that there are no missing numbers within an empty range.

When the input contains a single element, the set construction yields either {1} or {x} where x may be any integer. The loop runs once for the value 1. If the element is 1, the membership test succeeds and nothing is added to the result; otherwise 1 is identified as missing and appended, producing the correct single-element output.

Duplicate values in the input are collapsed by the set conversion, ensuring that the presence of repeated numbers does not affect the detection of missing values. For example, an input [2, 2, 3] yields a set {2, 3}; the loop then correctly identifies 1 as missing while ignoring the duplicate 2.

If the input list already contains all numbers from 1 to n, the membership test never fails, the result list remains empty, and the function returns an empty list, reflecting that no numbers are missing.

Performance Characteristics

The algorithm leverages a hash set to achieve constant-time checks for the existence of each candidate number. By avoiding nested loops or sorting, the implementation maintains a linear traversal over the numeric range, which scales directly with the size of the input. The use of a set also eliminates the need for auxiliary data structures proportional to the range size beyond the set itself, keeping the memory footprint modest.

The direct construction of the result list during the scan avoids any additional passes over the data, ensuring that each element is processed exactly once after the initial set creation. This design choice contributes to an efficient overall execution profile.

Imagine a toy box that should have a specific number of toys inside, numbered one through ten. Sometimes, some of those toys go missing and get lost under the bed. To find out which ones are gone, first, take all the toys currently in the box and put them into a special pile where it is very easy to check if a specific number exists. Then, start counting from one all the way up to the total number of toys that should be there. For every number counted, check if it is in the pile from the toy box. If that number is not in the pile, it means it is a missing toy, so write that missing number down on a piece of paper. Keep doing this for every number until the end of the count, and the paper will have a list of all the numbers that were not in the box.

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					Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	AdelDaniel										Dart
	BigEggStudy			C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	DimitrisJim						C
	everthis					JS
	fartem								Ruby
	FelixFan1122			C#
	fpdjsns	C++
	fsq		Python
	Garvit244		Python
	halfrost									Go
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	qiyuangong				Java
	ruoru							Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28				Java
	vli02						C
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
AdelDaniel	Dart
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
fsq	Python
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
zfang399	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