When the values are a permutation of a known range, the array is its own index. Put every value in its home slot and the anomalies name themselves.
This is the narrowest pattern on the site and the easiest to spot once you know it. It applies only when the numbers come from a bounded range like 1..n, but when it applies it beats sorting, beats hashing, and gives O(n) time with O(1) space.
n numbers drawn from a bounded range tied to n, usually 1..n or 0..n, and the question asks for the missing, duplicated, corrupted, or smallest absent value. Then add the constraint that seals it: O(n) time and O(1) space.| Signal | What it looks like |
|---|---|
| Range tied to length | “n distinct numbers in the range [0, n]”, “values are in 1 to n”, “a permutation of 1..n”. |
| Anomaly hunting | “find the missing one”, “find all missing”, “find the duplicate”, “the smallest positive not present”. |
| Space constraint | “O(1) extra space”, which forbids the obvious set or count array. |
1..n, then value v has an obvious home: index v - 1. Walk the array. If the value at i is not home, swap it to its home. Repeat at the same i until the value sitting there is already home, then move on. When the pass finishes, every index that does not hold its own value is an anomaly, and it points straight at the answer.Once the placement pass is done, one linear scan reads off the result. What you look for depends on the question.
| Question | After placement, look for |
|---|---|
| Which single value is missing? | The one index i where nums[i] != i (or != i + 1). |
| Which values are all missing? | Every such index, collected. |
| Which value is duplicated? | The value found sitting at a wrong index. |
| Smallest missing positive? | The first such index, converted back to a value. |
The loop has a while that sometimes does not advance i, so linearity needs an argument. It is short and interviewers like it.
n values, so there are at most n swaps in the whole run. Separately, i advances at most n times. Total work is at most 2n steps, so O(n).Put differently: the number of correctly placed values never decreases, and every non-advancing iteration increases it by at least one. The loop cannot spin.
def cyclic_sort(nums: list[int]) -> None:
"""Place every value v of 1..n at index v - 1, in place.
Args:
nums: A list whose values are in 1..len(nums). Mutated.
"""
i = 0
while i < len(nums):
home = nums[i] - 1 # where nums[i] wants to live
if nums[i] != nums[home]: # compare VALUES, not indices
nums[i], nums[home] = nums[home], nums[i]
else:
i += 1 # settled, or a duplicate; move on
For a 0..n range, drop the - 1: home = nums[i]. That is the only change.
nums[i] != nums[home] and not i != home. With duplicates the two differ. Take [2, 2]: at i = 0 the home is index 1, so i != home is true and you swap, getting [2, 2] again, forever. Comparing values instead notices that the destination already holds this value, so there is nothing to gain, and advances. This one line is the most common bug in the pattern.i after a swap. The value swapped into position i has not been examined yet. Only advance when nothing was swapped.0..n and 1..n. Write the home formula down before writing the loop.nums[i] - 1 can be negative or huge. Guard it.nums[i], nums[home] = nums[home], nums[i] is safe. The C-style three-line version with a temp is easy to get wrong when home depends on nums[i].An array nums holds n distinct numbers taken from the range 0..n. Exactly one number in that range is absent. Return it.
0..n, so the home of value v is index v, with no offset.n has no home, because the array only has indices 0..n-1. Skip it during placement; it simply sits wherever it lands.n itself was the missing one.def missing_number(nums: list[int]) -> int:
"""The one value of 0..n absent from nums.
Args:
nums: n distinct integers drawn from 0..n. Mutated in place.
Returns:
The missing value.
Example:
>>> missing_number([3, 0, 1])
2
"""
n = len(nums)
i = 0
while i < n:
home = nums[i] # 0..n range, so home == value
# n has no slot to go to, so leave it where it is.
if home < n and nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i]
else:
i += 1
for index in range(n):
if nums[index] != index:
return index
return n # every slot matched, so n is missing
nums = [3, 0, 1], n = 3:
| i | nums | action |
|---|---|---|
| 0 | [3, 0, 1] | home of 3 is 3, out of range, advance |
| 1 | [3, 0, 1] | home of 0 is 0, swap |
| 1 | [0, 3, 1] | home of 3 out of range, advance |
| 2 | [0, 3, 1] | home of 1 is 1, swap |
| 2 | [0, 1, 3] | home of 3 out of range, advance, done |
Scan: index 2 holds 3, mismatch, so the answer is 2.
def missing_number_gauss(nums: list[int]) -> int:
"""Subtract the actual sum from the expected sum."""
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
def missing_number_xor(nums: list[int]) -> int:
"""XOR every index and value; pairs cancel, the missing one survives."""
result = len(nums)
for index, value in enumerate(nums):
result ^= index ^ value
return result
nums = [0]: answer 1, from the final return n.nums = [1]: answer 0, from the scan.0.nums has n integers, each in 1..n. Some appear twice and some not at all. Return every value in 1..n that does not appear.
1..n home formula. Duplicates are handled by the value comparison: when a value tries to go home and finds a copy of itself already there, it stops trying.index + 1 for each.def find_disappeared_numbers(nums: list[int]) -> list[int]:
"""Every value of 1..n missing from nums.
Args:
nums: n integers in 1..n, with repeats allowed. Mutated in place.
Returns:
The absent values, in increasing order.
Example:
>>> find_disappeared_numbers([4, 3, 2, 7, 8, 2, 3, 1])
[5, 6]
"""
n = len(nums)
i = 0
while i < n:
home = nums[i] - 1
if nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i]
else:
i += 1
return [index + 1 for index in range(n) if nums[index] != index + 1]
[4, 3, 2, 7, 8, 2, 3, 1] becomes [1, 2, 3, 4, 3, 2, 7, 8] after placement. Indices 4 and 5 hold 3 and 2 instead of 5 and 6, so the answer is [5, 6]. Notice the leftover values at those slots are the duplicates, which is the next problem for free.
The output list is not counted as extra space, by the usual convention. Say that explicitly.
def find_disappeared_by_marking(nums: list[int]) -> list[int]:
"""Mark seen values by negating the value at their home index."""
for value in nums:
home = abs(value) - 1
if nums[home] > 0:
nums[home] = -nums[home]
return [i + 1 for i, value in enumerate(nums) if value > 0]
Same complexity, and it is the trick to reach for when values are positive and you want a one-pass mark. It destroys the values but keeps their magnitudes, so it is recoverable. Worth knowing as the sibling technique.
[].[1, 1, 1]: returns [2, 3].nums has n + 1 integers, each in 1..n. Exactly one value is repeated, possibly many times. Return it.
n + 1 slots but only n possible homes, so by the pigeonhole principle at least one slot must end up holding a value that is not its own.def find_duplicate(nums: list[int]) -> int:
"""The one repeated value in n + 1 integers drawn from 1..n.
Mutates nums. If the array must stay read-only, use Floyd's cycle
detection on the index graph instead.
Args:
nums: n + 1 integers in 1..n with exactly one repeated value.
Returns:
The repeated value.
Raises:
ValueError: If no duplicate is present.
Example:
>>> find_duplicate([1, 3, 4, 2, 2])
2
"""
i = 0
while i < len(nums):
home = nums[i] - 1
if nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i]
else:
i += 1
# Exactly one slot is left holding a value that is not its own.
for index, value in enumerate(nums):
if value != index + 1:
return value
raise ValueError("no duplicate found")
[1, 3, 4, 2, 2] settles to [1, 2, 3, 4, 2]. Index 4 should hold 5, which is out of range and never existed, and instead holds 2. That is the duplicate.
| Solution | Time | Space | Modifies | Use when |
|---|---|---|---|---|
| Cyclic sort placement | O(n) | O(1) | yes | Mutation is allowed. Easiest to explain. |
| Floyd on the index graph | O(n) | O(1) | no | The array is read-only. The intended answer on LeetCode. |
| Binary search on the value range | O(n log n) | O(1) | no | You want a read-only answer you can derive under pressure. |
[2, 2, 2, 2, 2]: still correct, because the swap loop stops as soon as a copy is already home.[1, 1]: answer 1.Given an unsorted array of integers, find the smallest positive integer that is not present. It must run in O(n) time and use O(1) extra space. Values may be negative, zero, or far larger than n.
n slots, the answer must lie in 1 .. n + 1. If the array happened to contain exactly 1, 2, …, n, the answer would be n + 1. Any other case leaves a gap below that. So every value outside 1..n is irrelevant: negatives, zeros, and anything above n can be ignored entirely. That single sentence turns an unbounded problem into a cyclic-sort problem.1..n at its home index. Guard the home index so out-of-range values are skipped rather than causing an IndexError or a wrap-around via a negative index.nums[index] != index + 1. That index plus one is the answer.1..n is present, so return n + 1.def first_missing_positive(nums: list[int]) -> int:
"""Smallest positive integer absent from nums, in O(n) time, O(1) space.
Args:
nums: Any integers, in any order. Mutated in place.
Returns:
The smallest positive integer not present. Always in 1..len(nums) + 1.
Example:
>>> first_missing_positive([3, 4, -1, 1])
2
"""
n = len(nums)
i = 0
while i < n:
home = nums[i] - 1
# Only values in 1..n have a home. The bounds check is what makes
# this safe for negatives, zeros and huge values.
if 0 <= home < n and nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i]
else:
i += 1
for index in range(n):
if nums[index] != index + 1:
return index + 1
return n + 1
nums = [3, 4, -1, 1], n = 4:
| i | nums | action |
|---|---|---|
| 0 | [3, 4, -1, 1] | 3 home is 2, swap with -1 |
| 0 | [-1, 4, 3, 1] | -1 has no home, advance |
| 1 | [-1, 4, 3, 1] | 4 home is 3, swap with 1 |
| 1 | [-1, 1, 3, 4] | 1 home is 0, swap with -1 |
| 1 | [1, -1, 3, 4] | -1 has no home, advance |
| 2, 3 | [1, -1, 3, 4] | 3 and 4 are already home, advance |
Scan: index 0 holds 1, fine. Index 1 holds -1, not 2. Answer 2.
0 <= home, a value of -5 gives home = -6, and Python happily indexes from the end of the list, corrupting the array silently rather than raising. That is a bug you will not see in a small test. Write the bounds check before the value comparison, and say why.[1, 2, 3]: nothing missing below n, so the answer is 4, from the final return.[7, 8, 9]: no value has a home, nothing moves, the answer is 1.n = 0, both loops skip, returns 1. Correct.[1, 1]: the value comparison stops the swap loop, answer 2.1.v lives at index v - 1 for a 1..n range, and at index v for a 0..n range.nums[i] != nums[home], never indices. Comparing indices loops forever on duplicates.i only when no swap happened. The value swapped in still needs checking.n swaps, because every swap permanently seats a value.Pattern 6, In-Place Reversal of a Linked List, is the last of the pointer-surgery patterns. Same spirit, no extra memory, but the state you carry is three pointers instead of an index.