Cyclic Sort

Cyclic sort is an in-place O(n)-time, O(1)-extra-space pattern for arrays that contain a permutation (possibly with one missing or duplicate value) of the integers 1..n (or 0..n-1). The core idea is so disarmingly simple it sounds like a trick: every value v should sit at index v - 1; if it doesn’t, swap it to its rightful home, and repeat. After a single linear sweep, every value is at its correct index, and any position whose value still doesn’t match betrays exactly the missing or duplicated number. The pattern collapses an entire family of LeetCode “find the missing/duplicate number in 1..n” problems into a single mechanical procedure that beats the obvious hash-set solution by a factor of n in extra space.

1. Intuition — Numbered Coat Hooks in a Cloakroom

Picture a cloakroom with n coat hooks numbered 1 through n, and n patrons holding numbered tickets 1..n. The coats have been hung on the hooks at random — patron 7’s coat dangles from hook 3, patron 3’s coat is on hook 9, and so on. Your job: get every coat onto its correct hook in a single walk down the row.

You walk to hook 1. You read the ticket number on the coat hanging there — say it’s 7. That coat belongs on hook 7, not hook 1. So you swap: you take the coat off hook 1, walk to hook 7, take whatever coat is hanging there (say it’s 3), put coat 7 on hook 7, and bring coat 3 back to hook 1. Now you read the ticket on hook 1 again — it’s 3. Coat 3 belongs on hook 3, not hook 1. Swap again: swap with hook 3. Keep going until the coat hanging on hook 1 reads 1. Then move on to hook 2.

That’s the entire algorithm. Every coat takes part in at most one swap that puts it home; once a coat is on its correct hook, no future iteration disturbs it. The total number of swaps is therefore at most n, and the total work across the whole sweep is O(n) even though it looks like there are nested loops.

When the array is a permutation of 1..n, every coat finds its hook and you end up with arr[i] == i + 1 everywhere. When one number is missing (replaced by a duplicate), exactly one hook ends up holding the wrong coat — and that hook’s index immediately reveals the missing number. This is the lever that solves an entire family of interview problems with the same template.

The pattern’s name “cyclic” sort comes from the structure of the swap chains: each swap is one step along a cycle in the permutation that maps index i to the index where arr[i] belongs. Following the cycle places every element on the cycle in the correct slot, and you advance to the next unprocessed index.

2. Tiny Worked Example

Take arr = [3, 1, 5, 4, 2] (a permutation of 1..5).

Each value v should live at index v - 1. We process indices left to right with a pointer i:

`i`	`arr` before	`arr[i]`	Target idx	Action	`arr` after
0	`[3, 1, 5, 4, 2]`	3	2	swap(0, 2)	`[5, 1, 3, 4, 2]`
0	`[5, 1, 3, 4, 2]`	5	4	swap(0, 4)	`[2, 1, 3, 4, 5]`
0	`[2, 1, 3, 4, 5]`	2	1	swap(0, 1)	`[1, 2, 3, 4, 5]`
0	`[1, 2, 3, 4, 5]`	1	0	matches, advance `i`	`[1, 2, 3, 4, 5]`
1	…	2	1	matches, advance `i`	unchanged
2..4	…	…	…	all match, advance	unchanged

Final array: [1, 2, 3, 4, 5]. Total swaps performed: 3. Notice index 0 was visited four times in the inner while loop, but each of those visits placed a different element into its final position. The total swap count across the entire run is bounded by n - 1 because each swap finalizes at least one element.

Now perturb the input: arr = [3, 1, 5, 4, 3] — value 2 is missing, value 3 appears twice. Run cyclic sort on it. Tracing through, you end with arr = [1, 3, 3, 4, 5]. Index 1 holds value 3, not the expected 2. So the missing number is 2 (the index + 1) and the duplicate is the value sitting wrongly at that index (3). This is the punchline: one O(n) sweep solves both “find missing” and “find duplicate” simultaneously.

3. The Pattern Recognition Signal

Reach for cyclic sort when all of the following hold:

The array contains values in the range 1..n or 0..n-1 where n = len(arr). This precondition is non-negotiable — if values can be arbitrary, cyclic sort doesn’t apply (you’d be indexing out of bounds with arr[arr[i] - 1]). Watch for the problem statement to say “an array of n integers, each in the range [1, n].”
The problem asks you to find a missing, duplicated, mismatched, or kth-missing element in such an array.
The problem demands O(1) extra space or pointedly says “without using a hash set” or “in O(n) time and O(1) space.” This rules out the obvious hash-set / counting-array solutions and forces you toward in-place techniques.

The inverse signals — when not to use cyclic sort:

Values aren’t in 1..n. A general unsorted array (values [-10⁹, 10⁹]) can’t index into itself; reach for Hash Table or sorting first. Cyclic sort is not a general-purpose sort.
Order matters and you can’t mutate. Cyclic sort destroys the input ordering. If you need to preserve it, copy first or use a hash.
You need stable sort semantics. Cyclic sort does not preserve relative order of equal elements.

The pattern is unusually narrow — but inside that narrow window it is the uniquely correct answer. Interviewers love it because the precondition “values are in 1..n” is a small piece of problem text that distinguishes the candidate who reads carefully (and recognizes the pattern) from the one who reaches reflexively for a hash set.

4. Pseudocode

cyclic_sort(arr):
    n := length(arr)
    i := 0
    while i < n:
        target := arr[i] - 1            # zero-indexed home of arr[i]
        if 0 <= target < n and arr[i] != arr[target]:
            swap(arr[i], arr[target])    # send arr[i] to its home
        else:
            i := i + 1                   # arr[i] is home, OR is a duplicate

Two subtle decisions are encoded here:

The arr[i] != arr[target] guard, not i != target. Using arr[i] != arr[target] rather than i != target is what makes the algorithm terminate even when the array contains duplicates (e.g., LC 287). If two indices both hold the value v, then arr[i] == arr[v - 1] after the first one is placed home; using the value-comparison form of the guard exits the inner loop instead of swapping forever. Using i != target would infinite-loop on duplicate input.

The bounds check 0 <= target < n. This protects against values outside the expected range. For the strict permutation problem (LC 268, 448) every value is in range, so the check is technically redundant but defensive. For “first missing positive” (LC 41) — where the array can contain negatives, zeros, and values larger than n — the bounds check is load-bearing; those out-of-range values are simply skipped because no position in 1..n is their correct home.

After the loop, scan once more: any index i with arr[i] != i + 1 is either a missing value (the index + 1 was never produced) or, if the value at that index is a repeat, the corresponding duplicate.

5. Python Implementation

5.1 The Pattern Itself

def cyclic_sort(arr: list[int]) -> None:
    """In-place sort assuming arr is a permutation of 1..n."""
    n = len(arr)
    i = 0
    while i < n:
        target = arr[i] - 1
        if 0 <= target < n and arr[i] != arr[target]:
            arr[i], arr[target] = arr[target], arr[i]
        else:
            i += 1

5.2 LC 268 — Missing Number (range `0..n`, one missing)

def missing_number(nums: list[int]) -> int:
    """Array contains n distinct numbers from [0, n] — find the missing one."""
    n = len(nums)
    i = 0
    while i < n:
        target = nums[i]                          # zero-indexed: value v lives at index v
        if target < n and nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n                                      # the missing number is n itself

The off-by-one in target = nums[i] (not nums[i] - 1) reflects the 0..n range: value 0 lives at index 0, value 1 at index 1, etc. The trailing return n covers the case where the missing number is n itself — the largest possible — and every index 0..n-1 ends up correctly placed.

5.3 LC 287 — Find the Duplicate Number (values `1..n`, length `n+1`, exactly one duplicate)

def find_duplicate_cyclic(nums: list[int]) -> int:
    """Array of length n+1 with values in [1, n] — exactly one duplicates."""
    n = len(nums)
    i = 0
    while i < n:
        target = nums[i] - 1
        if nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return nums[i]
    return -1                                     # unreachable per problem constraints

The nums[i] != nums[target] guard is doing essential work here: when the duplicate value d appears twice, after one of the copies is placed at index d - 1, the other copy sees nums[i] == nums[d - 1] and the loop advances instead of looping forever.

Constraint check — LC 287 forbids mutation

The official LC 287 statement is explicit: “You must solve the problem without modifying the array nums and using only constant extra space” (per the DesignGurus walkthrough of the official constraints; LeetCode itself blocks automated fetches). That hard constraint rules cyclic sort out as a conforming submission — it mutates the array — and steers you toward Floyd’s tortoise-and-hare on the index map (see Linked List Cycle Detection), which is O(n) time and genuinely O(1) space with no mutation. Cyclic sort remains a useful thinking tool for LC 287 and is accepted in interviews that don’t impose the no-mutation rule, but it is not the answer the problem as written wants.

5.4 LC 41 — First Missing Positive (general array, find smallest missing positive)

def first_missing_positive(nums: list[int]) -> int:
    """Smallest positive integer not in the array. Values can be anything."""
    n = len(nums)
    i = 0
    while i < n:
        target = nums[i] - 1
        if 0 <= target < n and nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

This is the harder cousin: the array contains arbitrary integers (negatives, zeros, values > n), but the answer must be in [1, n + 1] because if all of 1..n are present the answer is n + 1, and otherwise it’s whichever of 1..n is absent. The bounds check in the inner if quietly drops out-of-range values — they sit wherever they happen to land and the final scan ignores them.

5.5 LC 442 / 448 — All Duplicates / All Missing

def find_all_duplicates(nums: list[int]) -> list[int]:
    """Values in [1, n], each appears once or twice. Return all that appear twice."""
    n, i = len(nums), 0
    while i < n:
        target = nums[i] - 1
        if nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    return [nums[i] for i in range(n) if nums[i] != i + 1]
 
 
def find_all_disappeared(nums: list[int]) -> list[int]:
    """Values in [1, n]. Return all values in [1, n] missing from the array."""
    n, i = len(nums), 0
    while i < n:
        target = nums[i] - 1
        if nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    return [i + 1 for i in range(n) if nums[i] != i + 1]

The two functions are literally identical except for what they emit in the final list comprehension: nums[i] (the value at the wrong slot — i.e., the duplicate) versus i + 1 (the value that should have been there — i.e., the missing). One pattern, two problems for the price of one.

6. Complexity

Time: O(n) amortized. The outer while i < n loop iterates at most n times. The inner swap also happens, but each swap places one element in its final position — and once an element is placed, no future swap moves it. So across the entire algorithm there are at most n - 1 swaps. The total work is n (outer iterations) + n - 1 (swaps) + n (final scan) = O(n). The nested loop look-and-feel is misleading; it’s a textbook example of why amortized analysis matters.

A more precise argument: define a potential function Φ = number of elements not yet at their correct index. Initially Φ ≤ n. Each swap that moves a value v to position v - 1 strictly decreases Φ by at least one (the swapped-in element from arr[v - 1] may or may not now be at home; the swapped-out value v definitely is). Each i += 1 step increases the progress index but doesn’t increase Φ. The total number of swaps across the run is therefore bounded by the initial Φ ≤ n.

Space: O(1) extra. All operations are in-place. The recursion-free iterative form uses only the integer pointer i and the integer target; the swap is constant-space.

This O(n)/O(1) bound is the entire reason cyclic sort exists. The competing approaches:

Hash set — O(n) time, O(n) space. Simple, idiomatic, but loses the space competition.
Sort then scan — O(n log n) time, O(1) or O(log n) space (depending on sort). Loses the time competition.
Bit-vector counting — O(n) time, O(n) bits = O(n) space (lower constant than a hash set, but still linear).
Cyclic sort — O(n) time, O(1) space, with the constant-factor cost of mutating the input.

Only the XOR trick for “missing one number” matches cyclic sort on both axes, but XOR doesn’t generalize beyond exactly-one-missing scenarios; cyclic sort handles missing-and-duplicate and first-missing-positive in the same template.

7. Comparison with Hash-Set / Counting-Array Approaches

The pedagogical reason cyclic sort matters in interviews is the contrast with the obvious hash-set approach. Walk through “Find the Missing Number” (LC 268) under both lenses:

Hash-set approach.

def missing_hash(nums: list[int]) -> int:
    s = set(nums)
    for i in range(len(nums) + 1):
        if i not in s:
            return i

O(n) time, O(n) space. Clean, obvious, but consumes ~n × 28 bytes of extra memory for the Python set (each int in a set carries object header overhead). On a 10⁸-element array that’s gigabytes of RAM you didn’t need.

Cyclic sort approach. O(n) time, O(1) extra space. Same asymptotic time, dramatically better space, at the cost of mutating the input array.

The interviewer is rarely just checking that you can solve the problem — they’re checking whether you noticed the “values are in 1..n” precondition and recognized that it unlocks an in-place solution. Naming the cyclic-sort pattern out loud during whiteboard discussion is the signal that you’ve internalized when index-as-key tricks apply.

A related but distinct technique is negate-as-marker (used for LC 442 if you don’t want to mutate the order): walk the array, for each value v set arr[abs(v) - 1] = -abs(arr[abs(v) - 1]) to mark v as seen. Indices with positive values at the end are the missing ones; values seen twice produce two negation attempts on the same cell. This is also O(n)/O(1) but mutates the signs of the values, which the cyclic-sort approach doesn’t (it only reorders them). Both are legitimate; cyclic sort generalizes more cleanly to the broader family.

8. Variants and Extensions

8.1 Find the Smallest k Missing Positive Numbers

Cyclic sort the array (using only positive values in range), then walk indices to enumerate the first k indices with arr[i] != i + 1. The values i + 1 for such indices are the missing positives in ascending order. If you exhaust the array before finding k of them, continue beyond n (the next missing positive is n + 1, then n + 2, etc., skipping any values you’ve seen in the array).

8.2 Find the Mismatched Pair

Given an array of 1..n with one value duplicated (replacing one missing), cyclic sort and scan: the index with arr[i] != i + 1 gives both — the missing is i + 1, the duplicate is arr[i] (LC 645).

8.3 Cycle Sort vs. Cyclic Sort the Pattern

The classical Cycle Sort algorithm (Wikipedia article cited in sources) is a different, more general in-place sorting algorithm by W. D. Maurer that minimizes the number of writes to the array — important for media with limited write endurance like flash memory. The “cyclic sort pattern” used in interview prep (Educative.io’s framing, widely adopted) is a specialization for the 1..n permutation case. The patterns share the underlying intuition (follow the permutation cycles) but the interview pattern is much narrower and simpler.

Naming — community vocabulary, not a textbook term

The interview-prep “cyclic sort pattern” is a popularization by Grokking-the-Coding-Interview-style courses (the Educative.io framing cited in sources). The underlying cycle decomposition of a permutation is standard mathematics, and the write-minimizing Cycle Sort of W. D. Maurer is a real published algorithm (Wikipedia: Cycle sort) — but “cyclic sort, the 1..n interview pattern” under that exact name is community vocabulary, not terminology you will find in CLRS or Sedgewick. Use the name to communicate with other interview-prep readers; don’t expect an academic to recognize it. (This is a claim about naming convention, not a verifiable fact about the algorithm — left unresolved because proving a textbook does not contain a term is not cleanly citable.) uncertain

9. Pitfalls

9.1 Wrong Termination Guard Causes Infinite Loop on Duplicates

Using if i != target instead of if arr[i] != arr[target] works for strict permutations but infinite-loops on inputs with duplicates: when value v appears twice and one copy is already at index v - 1, the second copy sees target == v - 1 (i != target true) and swaps with itself forever. Always use the value-comparison form unless you can prove the input has no duplicates.

9.2 Forgetting the Bounds Check on `target`

For LC 41 (first missing positive), values can be negative, zero, or > n, all of which produce target outside [0, n). Without the 0 <= target < n guard, you index out of bounds (IndexError in Python, segfault in C). The bounds check is what lets the same pattern transparently handle “general” arrays — values that don’t belong to any slot in 1..n are silently skipped.

9.3 Mixing 1-Indexed and 0-Indexed Conventions

Half the variants use target = arr[i] - 1 (1-indexed values living at 0-indexed positions; the 1..n family) and half use target = arr[i] (0-indexed values; the 0..n-1 or 0..n family, e.g., LC 268). Mismatching the convention to the problem’s value range produces silent off-by-one bugs that pass small tests and fail edge cases. Re-derive the indexing relationship from the problem’s stated value range every time; don’t paste from memory.

9.4 Mutating the Input When Forbidden

Some problem variants (LC 287 in particular) explicitly forbid modifying the input. Cyclic sort requires mutation. If the constraint binds, switch to Floyd’s cycle detection on the index map (Linked List Cycle Detection) or to negate-as-marker (which still mutates but only signs).

9.5 Assuming the Pattern Works for General Arrays

Cyclic sort is not a general-purpose sort competitive with Quicksort, Merge Sort, or Heap Sort on arbitrary arrays. Its O(n) bound depends crucially on the value-equals-index-plus-one structure. On general arrays you cannot index into arr[arr[i] - 1] meaningfully and the swap chain has no termination guarantee. Cyclic sort is a pattern that exploits a specific structural precondition, not a sort to keep in your back pocket for arbitrary inputs.

9.6 Off-by-One in the Final Scan

After cyclic sort, the diagnostic scan compares arr[i] against i + 1 (for the 1..n family) or i (for the 0..n-1 family). Getting this wrong reports the wrong missing value by exactly one. Pair it mentally with the indexing convention you chose for target.

10. Diagram — One Sweep, Several Cycles

flowchart LR
    subgraph cycle1 ["Cycle: 0 → 2 → 4 → 1 → 0"]
        i0["arr[0]=3"] -->|target=2| i2["arr[2]=5"]
        i2 -->|target=4| i4["arr[4]=2"]
        i4 -->|target=1| i1["arr[1]=1"]
        i1 -->|home| done0["arr[0]=1 ✓"]
    end
    subgraph cycle2 ["Self-loop"]
        i3["arr[3]=4"] -->|target=3, already home| done3["arr[3]=4 ✓"]
    end

What this diagram shows. Cyclic sort’s name comes from this picture: the permutation [3, 1, 5, 4, 2] decomposes into cycles when viewed as the function f(i) = arr[i] - 1. Index 0 maps to index 2 (because arr[0] = 3), which maps to index 4 (because arr[2] = 5), which maps to index 1 (because arr[4] = 2), which maps to index 0 (because arr[1] = 1) — a 4-cycle. Index 3 is a fixed point (arr[3] = 4, target = 3, already home — a 1-cycle). Cyclic sort, starting at index 0, follows the long cycle one swap at a time, depositing each value at its destination as it goes. Each swap takes the “current” value of arr[0] and exchanges it with the value at the target index; the next iteration’s swap reads the new arr[0] and continues along the cycle. After traversing the cycle, arr[0] holds value 1 (home). Index 3 is hit by the outer pointer, found already home, and skipped. Total swaps for this 4-cycle: 3. In general, a cycle of length k takes k - 1 swaps to resolve, and the sum of cycle lengths is n, so the total swap count is n - (number of cycles) ≤ n - 1.

11. Common Interview Problems

#	Problem	Range	What cyclic sort tells you
LC 268	Missing Number	`[0, n]`	The single missing element
LC 41	First Missing Positive	arbitrary, answer in `[1, n+1]`	Smallest absent positive
LC 287	Find the Duplicate Number	`[1, n]`, length `n+1`	The single duplicate (if mutation allowed)
LC 442	Find All Duplicates	`[1, n]`, each 1–2 times	Every duplicated value
LC 448	Find All Numbers Disappeared	`[1, n]`	Every missing value
LC 645	Set Mismatch	`[1, n]`, one duplicate replaces one missing	Both the duplicate and the missing
LC 765	Couples Holding Hands	`[0, 2n)`	Greedy + cycle-following counts swaps
LC 1539	Kth Missing Positive Number	sorted positives	Variant: index-vs-value gap reveals position
LC 2471	Min Swaps to Sort by Level	per-level permutation	Cycle decomposition of a permutation gives min swaps = `n − cycles`

The last entry is worth highlighting separately: the minimum number of swaps to sort any permutation equals n minus the number of cycles in its cycle decomposition. Cyclic sort is essentially performing this minimum-swap procedure in disguise — every swap reduces the number of misplaced elements by at least one, and you can’t do better than n − cycles.

12. Open Questions

Is there a clean generalization of cyclic sort to value ranges [a, a + n - 1] for arbitrary a? Trivially yes (subtract a), but it loses the elegance — and now you need O(n) preprocessing space to remember the offset, defeating the point.
How does cyclic sort interact with cache hierarchies vs. sequential sorts? The swap pattern is inherently random-access (jumping to arr[arr[i] - 1]), which is bad for cache locality compared to a streaming radix sort. For very large n, Counting Sort or Radix Sort on bounded-range data may dominate empirically despite worse asymptotics on extra space.
Is there a parallel version? Each cycle is independent, so cycles could in principle be processed in parallel — but discovering cycles in parallel itself takes work, and it’s unclear whether you net out ahead vs. a parallel sort.

13. See Also

Two Pointers — sibling in-place pattern; cyclic sort uses one pointer plus a “compute target index” rule
Linked List Cycle Detection — Floyd’s tortoise-and-hare on the index map is the alternative for LC 287 when mutation is forbidden
Hash Table — the O(n)-space alternative cyclic sort displaces
Quicksort — another in-place sort, but general-purpose; cyclic sort is range-restricted
Counting Sort — also exploits bounded value range, but uses O(k) extra space rather than mutating in place
Big-O Notation — for the amortized O(n) argument
SWE Interview Preparation MOC

vault

Explorer

Cyclic Sort

Cyclic Sort

1. Intuition — Numbered Coat Hooks in a Cloakroom

2. Tiny Worked Example

3. The Pattern Recognition Signal

4. Pseudocode

5. Python Implementation

5.1 The Pattern Itself

5.2 LC 268 — Missing Number (range `0..n`, one missing)

5.3 LC 287 — Find the Duplicate Number (values `1..n`, length `n+1`, exactly one duplicate)

5.4 LC 41 — First Missing Positive (general array, find smallest missing positive)

5.5 LC 442 / 448 — All Duplicates / All Missing

6. Complexity

7. Comparison with Hash-Set / Counting-Array Approaches

8. Variants and Extensions

8.1 Find the Smallest k Missing Positive Numbers

8.2 Find the Mismatched Pair

8.3 Cycle Sort vs. Cyclic Sort the Pattern

9. Pitfalls

9.1 Wrong Termination Guard Causes Infinite Loop on Duplicates

9.2 Forgetting the Bounds Check on `target`

9.3 Mixing 1-Indexed and 0-Indexed Conventions

9.4 Mutating the Input When Forbidden

9.5 Assuming the Pattern Works for General Arrays

9.6 Off-by-One in the Final Scan

10. Diagram — One Sweep, Several Cycles

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Cyclic Sort

Cyclic Sort

1. Intuition — Numbered Coat Hooks in a Cloakroom

2. Tiny Worked Example

3. The Pattern Recognition Signal

4. Pseudocode

5. Python Implementation

5.1 The Pattern Itself

5.2 LC 268 — Missing Number (range 0..n, one missing)

5.3 LC 287 — Find the Duplicate Number (values 1..n, length n+1, exactly one duplicate)

5.4 LC 41 — First Missing Positive (general array, find smallest missing positive)

5.5 LC 442 / 448 — All Duplicates / All Missing

6. Complexity

7. Comparison with Hash-Set / Counting-Array Approaches

8. Variants and Extensions

8.1 Find the Smallest k Missing Positive Numbers

8.2 Find the Mismatched Pair

8.3 Cycle Sort vs. Cyclic Sort the Pattern

9. Pitfalls

9.1 Wrong Termination Guard Causes Infinite Loop on Duplicates

9.2 Forgetting the Bounds Check on target

9.3 Mixing 1-Indexed and 0-Indexed Conventions

9.4 Mutating the Input When Forbidden

9.5 Assuming the Pattern Works for General Arrays

9.6 Off-by-One in the Final Scan

10. Diagram — One Sweep, Several Cycles

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

5.2 LC 268 — Missing Number (range `0..n`, one missing)

5.3 LC 287 — Find the Duplicate Number (values `1..n`, length `n+1`, exactly one duplicate)

9.2 Forgetting the Bounds Check on `target`