Cyclic Sort Pattern: Find Missing and Duplicate Numbers in O(1) Space

The cyclic sort pattern places each number at the index it belongs to (value v at index v - 1) by swapping in place, then scans for positions that hold the wrong value. Use it when an array of length n contains numbers from a known range like 1..n or 0..n and the problem asks for missing numbers, duplicates or the first missing positive in O(n) time and O(1) extra space.

It is one of the most specific patterns in coding interviews: the signal is narrow, but when it fits, it turns a hash set solution into a constant-space one. This guide gives you the signals, a Python template, three worked LeetCode problems, a complexity table and a practice list. Every snippet below was run against test cases in Python before we published it.

When to use the cyclic sort pattern

• Values in a known range tied to the length. "Integers in the range [1, n]" or "n distinct numbers in [0, n]." That range is what lets every value map to its own index.
• The question is about what is missing or repeated. Missing number, all missing numbers, duplicates, the corrupt pair, the first missing positive.
• O(1) extra space is required (or asked in the follow-up). A set would solve it, so the constraint is the hint.
• You are allowed to modify the input. Cyclic sort rearranges the array. If the problem says "do not modify the array," use a different pattern.

The last point matters. Find the Duplicate Number (LeetCode 287) has values in [1, n] but forbids modifying the array, so it is solved with the fast and slow pointers pattern instead.

The cyclic sort template in Python

def cyclic_sort(nums):                 # values are 1..n
    i = 0
    while i < len(nums):
        correct = nums[i] - 1          # index where nums[i] belongs
        if nums[i] != nums[correct]:   # not already there (also stops on duplicates)
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1                     # placed, or a duplicate: move on
    return nums

Two details make this correct:

1. Do not advance i after a swap. The value you just swapped in may also be out of place, so check index i again.
2. Compare values, not indices. The condition nums[i] != nums[correct] is false both when the value is already home and when its home already holds a copy of it. That second case is what prevents an infinite loop when there are duplicates.

Why it is O(n): every swap puts at least one value into its final position, and a value never leaves its final position. So there are at most n swaps in total, plus n increments of i. The while loop looks nested-ish, but the total work is linear.

Worked problems

1. Find All Numbers Disappeared in an Array (LeetCode 448, Easy)

Problem: nums has n integers, each in [1, n]. Return every number in [1, n] that does not appear. The follow-up asks for O(n) time without extra space (the output list does not count). See LeetCode 448.

Idea: run the template. Afterward, index i holds i + 1 unless i + 1 is missing; in that case it holds some duplicate.

def find_disappeared(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    return [i + 1 for i, x in enumerate(nums) if x != i + 1]

Time: O(n). Space: O(1) besides the output.

One-line variant: Find All Duplicates in an Array (LeetCode 442, Medium), where each value appears once or twice, uses the same sort and returns x instead of i + 1: [x for i, x in enumerate(nums) if x != i + 1]. Each misplaced value is the second copy of a duplicate.

2. Set Mismatch (LeetCode 645, Easy)

Problem: a set that should contain 1..n has one number duplicated, which replaced another number. Return [duplicate, missing].

Idea: after the sort exactly one index is wrong. Its index tells you the missing number and its value is the duplicate, so one scan returns both.

def find_error_nums(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    for i, x in enumerate(nums):
        if x != i + 1:
            return [x, i + 1]          # [duplicate, missing]

Time: O(n). Space: O(1). A counting array also works in O(n) space; cyclic sort is the answer when the interviewer asks for constant space.

3. First Missing Positive (LeetCode 41, Hard)

Problem: given an unsorted integer array, return the smallest positive integer that is not present, in O(n) time and O(1) auxiliary space. Values can be negative, zero or huge. See First Missing Positive.

Idea: the answer is always in 1..n+1, because n numbers can fill at most the slots 1..n. So ignore any value outside 1..n, cyclic-sort the rest, and return the first index whose value is wrong. If every slot is correct, the answer is n + 1.

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        j = nums[i] - 1
        if 0 <= j < n and nums[i] != nums[j]:   # skip values outside 1..n
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Time: O(n). Space: O(1). This is the problem where cyclic sort is clearly the best tool: the in-place constraint rules out a set, and sorting would be O(n log n).

Cyclic sort complexity table

Negative marking is the main alternative interviewers bring up for LeetCode 448 and 442; it is worth knowing both. For Missing Number (LeetCode 268), where exactly one value in 0..n is absent, the sum or XOR trick is simpler than cyclic sort, so mention it first. See the Big-O cheat sheet if the table's growth rates need a refresher.

Common bugs and edge cases

• The Python swap trap. nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i] is wrong: Python assigns nums[i] first, so the second target index is computed from the new value. Store the target index in a variable (j) first, as the code above does.
• Infinite loop on duplicates. Comparing nums[i] != i + 1 instead of nums[i] != nums[j] keeps swapping two equal values forever.
• Advancing i after every swap. The new value at i may also be misplaced; only advance when nothing moved.
• 0-based vs 1-based ranges. For 1..n the home index is v - 1; for 0..n it is v, and the value n has no slot, so skip it.
• Out-of-range values. In First Missing Positive, guard with 0 <= j < n before indexing, or negative numbers will index from the end of the list in Python without any error.
• Read-only input. If the array must not change, cyclic sort is off the table.

Practice list: 6 cyclic sort problems

Difficulty labels are LeetCode's own, checked as of October 2026.

For the full map of patterns, see 15 LeetCode patterns for interviews, the two pointers pattern and the binary search patterns guide (Kth Missing Positive Number is a binary search problem, not cyclic sort). The coding interview cheat sheet lists them on one page.

How to practice cyclic sort

Do 448, 645 and 41 in one sitting. They share the same loop, and the only change is the guard and the final scan. Then explain the O(n) argument and the duplicate guard out loud, because those are the two follow-ups that come up most often with this pattern.

CoPilot Interview's Mock Interview can run a coding round from your résumé and the job description and score each spoken answer out of 10 with what to fix and a model answer. The browser AI mock interview needs no install and includes a coding track.

FAQ

What is the cyclic sort pattern?

Cyclic sort is an in-place technique for arrays whose values fall in a known range such as 1 to n. It swaps each value to its home index (value v at index v - 1), then scans for indices holding the wrong value to find missing or duplicate numbers in O(n) time and O(1) extra space.

When should I use cyclic sort?

Use it when the array length and the value range are tied together, for example n numbers in the range 1 to n or 0 to n, and the question asks for missing numbers, duplicates or the first missing positive with constant extra space. You must be allowed to modify the array.

Why is cyclic sort O(n) if it has a while loop with swaps?

Each swap places at least one value in its final position, and that value never moves again, so there are at most n swaps. Together with at most n increments of the index, the total work is linear.

How does cyclic sort handle duplicates?

The swap condition compares the value with the value already at its home index. If they are equal, the home is taken by a copy, so the loop advances instead of swapping forever. After the sort, duplicates sit at indices whose correct value is missing.

Can I use cyclic sort for Find the Duplicate Number?

Not under LeetCode 287's rules, because it forbids modifying the array and cyclic sort swaps values in place. Use Floyd's fast and slow pointers on the implicit linked list from index i to nums[i] instead.

Which LeetCode problems use cyclic sort?

Missing Number (268), Find All Numbers Disappeared in an Array (448), Set Mismatch (645), Find All Duplicates in an Array (442) and First Missing Positive (41) are the core set.