Abstract / Summary

Given an array of integers, identify the number that appears twice and the number that is missing from the sequence.

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 83% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Math
• Matrix

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 locating a single repeated value and a single missing value in an n × n matrix that should contain every integer from 1 through n² exactly once. The algorithm walks through the matrix once, builds a record of values that have already been observed, and simultaneously maintains a collection of values that are still expected. At the end of the traversal the repeated value and the missing value are extracted and returned as a two-element list.

Core Logic

The first step determines the dimension of the square matrix and prepares two auxiliary sets. One set, called have, accumulates numbers that have been encountered. The second set, called need, is initialized with the complete range of values that should appear in the matrix.

n     = len(grid)
have  = set()
need  = set(range(1, n * n + 1))

The algorithm then iterates over each row and each element within the row. For every element r it checks whether the element is already present in have. If the element is found, it is identified as the repeated value and stored in the variable twice. Regardless of duplication, the element is added to have and removed from need. The removal uses discard, which silently does nothing if the element is not present, thereby avoiding unnecessary error handling.

for row in grid:
    for r in row:
        if r in have:
            twice = r
        have.add(r)
        need.discard(r)

After the nested loops finish, need contains exactly one element-the value that never appeared in the matrix. The method extracts this element with pop and returns both the repeated and missing values.

return [ twice, need.pop() ]

Edge-Case Handling

The code gracefully handles the situation where the duplicate appears more than twice. The condition if r in have: will be true for every occurrence after the first, and the variable twice will be overwritten each time. Consequently, twice ends up holding the duplicated value regardless of how many times it repeats, satisfying the requirement that only one value is duplicated.

When the missing value is the smallest or largest possible integer, the initialization of need with the full range guarantees that it will still be present after all discards. The use of discard ensures that attempts to remove a value that is already absent (which could happen if the matrix contains an out-of-range number) do not raise an exception, keeping the algorithm robust against unexpected inputs.

If the input matrix is empty (n == 0), the range for need becomes empty as well, and the loops simply do not execute. In that scenario the function would attempt to pop from an empty set, which would raise an exception. However, under the problem’s contract the matrix is always a non-empty square containing numbers from 1 to n², so this edge case is outside the intended domain.

Performance Optimizations

The implementation leverages the constant-time membership test of Python’s built-in set type. By checking if r in have: and performing have.add(r), the algorithm avoids any linear scans that would be required with a list or array. The simultaneous maintenance of the need set eliminates the need for a separate pass to locate the missing number; each element is removed from need as soon as it is seen, leaving only the absent value at the end.

Using discard instead of remove for the need set is a subtle optimization. discard does not raise an exception when the element is absent, which removes the overhead of exception handling in the common case where every element is present exactly once. This choice streamlines the inner loop and keeps the execution path tight.

The algorithm processes the matrix in a single nested loop, achieving a linear scan over all n² entries. By avoiding auxiliary data structures beyond the two sets, the memory footprint remains proportional to the number of distinct values, which is optimal for this problem. The final extraction of the missing value with pop is an O(1) operation, completing the computation without additional traversal.

Imagine a giant box filled with smaller boxes, and inside each small box is a number. Everything is a bit messy because some numbers are playing hide and seek.

First, look at how many small boxes there are in total. This helps figure out which numbers should be there. Imagine a complete set of stickers from one to the very last number.

Now, walk through every single row and peek inside each small box one by one. When a number is found, write it down on a piece of paper to remember that it was seen. If a number is found that is already on the paper, that is the duplicate number.

At the same time, keep a list of all the numbers that are supposed to be in the set. Every time a number is found in the grid, cross it off that list.

After checking every single box, the duplicate number is the one seen twice. The number that is still left on the list is the one that got lost and was never found. These two special numbers are the ones being hunted.

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

Time: polynomial
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		Java			C++	Python	TS
	WalkCCC		Java			C++	Python
	leetcode.ca		Java	Go		C++	Python	TS
	Progiez		Java			C++	Python
github	charles-wangkai		Java
	everthis	JS
	fsq					C++
	JoshCrozier	JS
	muhammadfarhankt			Go
	Shamik07				Dart
	varunu28		Java
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++
JoshCrozier	JavaScript
muhammadfarhankt	Go
Shamik07	Dart
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