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 # 0: start scanning at the first slot
# i is the slot we are fixing. Invariant: slots 0..i-1 are settled
# (each holds its own value, or a duplicate whose home is taken).
while i < len(nums):
# - 1: values are 1-based, indices are 0-based. Value v lives at v - 1.
home = nums[i] - 1 # where nums[i] wants to live
# If home already holds the same value, a swap would loop forever.
if nums[i] != nums[home]: # compare VALUES, not indices
# Each swap puts one value in its final slot, so at most n swaps.
# Do not advance i: a new value just landed here and needs a home.
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.
i when a swap would gain nothing, which is what stops it looping on duplicates.Reading the figure. The amber box is slot i. Green means the value sits at its home, index v - 1. Red means it does not. The purple arrow is the swap, from slot i to the home of its value. On the left, a swap brings in a new value, so i stays put. On the right, the home already holds a 2, so the loop gives up on this copy and moves on.
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) # n slots, but n + 1 possible values 0..n
i = 0 # 0: start at the first slot
# Invariant: slots 0..i-1 hold their own value, or hold n (no home).
while i < n:
# No - 1 here: values start at 0, so value v lives at index v.
home = nums[i] # 0..n range, so home == value
# n has no slot to go to, so leave it where it is.
# home < n guards the index. nums[i] != nums[home] stops a self-swap.
if home < n and nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i] # one value lands for good
else:
i += 1 # this slot is done. Move to the next
# Every value is now home. The first slot that does not hold its own
# index is the hole left by the missing value.
for index in range(n): # range(n): check slots 0..n-1
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.
Reading the figure. Each row is the array at one step. The amber box is slot i. Green values sit at home, which is index v here. Grey marks 3, which has no index to live at. The purple arrow sends a value home. Notice that 3 drifts right with each swap and ends in the slot that 2 should own.
def missing_number_gauss(nums: list[int]) -> int:
"""Subtract the actual sum from the expected sum."""
n = len(nums) # n numbers, so the full range is 0..n
# n * (n + 1) // 2: Gauss sum of 0..n. // 2 is exact since n * (n + 1) is even.
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."""
# Start with n: indices only reach n - 1, so n must be added by hand.
result = len(nums)
# Invariant: result is the XOR of n and every index and value seen so far.
for index, value in enumerate(nums): # enumerate starts at 0: indices 0..n-1
result ^= index ^ value # x ^ x == 0, so matched pairs vanish
return result # only the unpaired missing value is left
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) # n slots for values 1..n
i = 0 # 0: start at the first slot
# Invariant: slots 0..i-1 hold their own value, or a duplicate.
while i < n:
home = nums[i] - 1 # - 1: value v lives at index v - 1
# Equal values mean home is taken (or this IS home). Swapping would loop.
if nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i] # place one value for good
else:
i += 1 # settled or a duplicate. Move on
# A slot that does not hold index + 1 is the home of a missing value.
# + 1 turns the 0-based index back into its 1-based value.
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.
Reading the figure. Green slots hold their own value, v at index v - 1. Red slots hold a value that belongs elsewhere. After placement only two red slots remain. Each one reads off as index + 1, the value that never showed up.
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."""
# value is the next number read. Invariant: for every value seen so far,
# the number at its home index is negative.
for value in nums:
# abs: an earlier pass may have negated this slot already.
# - 1: value v lives at index v - 1.
home = abs(value) - 1
if nums[home] > 0: # > 0: not yet marked
nums[home] = -nums[home] # negate = "home of v was seen"
# A slot still > 0 was never marked, so its value i + 1 never appeared.
# + 1 turns the 0-based index back into its 1-based value.
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 # 0: start at the first slot
# Invariant: slots 0..i-1 hold their own value, or the duplicate.
while i < len(nums):
home = nums[i] - 1 # - 1: value v lives at index v - 1
# Equal values: home is taken, so nums[i] is settled or the duplicate.
if nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i] # place one value for good
else:
i += 1 # nothing to swap. Move on
# Exactly one slot is left holding a value that is not its own.
for index, value in enumerate(nums): # enumerate from 0: 0-based indices
if value != index + 1: # + 1: slot index should hold index + 1
return value # the extra copy that found no home
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.
Reading the figure. The amber box is slot i. Green values are home, red values are not. The purple arrow sends a value to index v - 1. In the last row the 2 at index 4 tries to go home, finds a 2 already there, and stays. It is the only red cell, so it is the answer.
| 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) # n slots: only values 1..n can matter
i = 0 # 0: start at the first slot
# Invariant: slots 0..i-1 hold their own value, or junk that has no home.
while i < n:
home = nums[i] - 1 # - 1: value v lives at index v - 1
# Only values in 1..n have a home. The bounds check is what makes
# this safe for negatives, zeros and huge values.
# 0 <= home < n is the same as 1 <= value <= n.
if 0 <= home < n and nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i] # place one value for good
else:
i += 1 # junk, duplicate, or settled. Move on
# The first slot not holding index + 1 names the answer.
for index in range(n): # range(n): check slots 0..n-1
if nums[index] != index + 1: # + 1: slot index should hold index + 1
return index + 1 # + 1: back to the 1-based value
return n + 1 # 1..n all present, so n + 1 is missing
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.
Reading the figure. The amber box is slot i. Green values are home at index v - 1. Grey marks -1, which has no home, so the bounds check skips it. The purple arrow sends a value home. In the scan row, red marks the first slot that does not hold index + 1. Its index plus one is the smallest missing positive.
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.