Cyclic Sort Interview Pattern: Missing and Duplicate Numbers in O(n)

Cyclic Sort Interview Pattern: Missing and Duplicate Numbers in O(n)

Some interview problems look like they need a hash set or a sort, but the interviewer then asks for O(n) time and O(1) extra space. When the input is an array of numbers in a known range, like 1 to n or 0 to n, that follow-up usually points to one idea: cyclic sort.

This guide explains the cyclic sort interview pattern, how to recognize it, the core loop, and how to talk through it clearly.

How to recognize the pattern

Look for these signals:

Classic examples:

The core idea

If the values are in the range 1..n, each value has a "home" index: value v belongs at index v - 1. Cyclic sort walks through the array and keeps swapping the current value into its home until the current position holds the right value, or holds a value that can't be placed.

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    return nums

Why it's O(n): every swap puts at least one number in its final place. There can be at most n such placements, so the total number of swaps is bounded by n, even though there's a loop inside a loop in spirit.

Why compare values, not indices: checking nums[i] != nums[correct] instead of i != correct prevents infinite loops when there are duplicates. If the home slot already holds the same value, we move on.

Example 1: Find all missing numbers in 1..n

After cyclic sort, any index i where nums[i] != i + 1 is a spot whose rightful value is missing.

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

Example 2: Find the duplicates

Same sort; now the value sitting in a wrong spot is the duplicate.

def find_duplicates(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    return [nums[i] for i in range(len(nums)) if nums[i] != i + 1]

Example 3: First missing positive

Here the array can contain negatives, zeros, and numbers larger than n. The trick is to only place values that fall in 1..n and ignore the rest.

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        v = nums[i]
        if 1 <= v <= n and nums[v - 1] != v:
            nums[i], nums[v - 1] = nums[v - 1], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

This is a well-known hard problem, and cyclic sort turns it into a short, explainable solution.

Talk track for the interview

  1. Name the range observation: "The values are between 1 and n, so each value has a natural index."
  2. Explain the placement: "I'll swap each number into its home index until the current slot is settled."
  3. Justify complexity: "Each swap fixes at least one element, so total swaps are at most n. Time is O(n), extra space O(1)."
  4. Explain the scan: "After placement, any index that doesn't hold its value tells me what's missing or duplicated."
  5. Mention the trade-off: "This modifies the input. If that's not allowed, I'd use a hash set with O(n) space, or restore the array afterward."

Common bugs

Mentioning one of these shows you understand the space of solutions, not just one template.

Practice the explanation, not just the code

Cyclic sort is short to write but easy to fumble when nervous, especially the loop condition. Luna Interview helps you rehearse explaining patterns like this out loud and under time pressure, so the reasoning comes out clearly in the real round.

Solve the five classic problems above twice each, saying the talk track out loud, and this pattern will stick.