Cyclic Sort Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When an interview problem tells you that an array contains distinct integers drawn from a known consecutive range, the most efficient way to reorder it is often a cyclic sort. The idea is simple: each value belongs at the index equal to its "target" position. By repeatedly swapping a misplaced element into its correct slot, you can finish the whole array in a single pass.

Why Cyclic Sort Exists

Traditional sorting algorithms (quick‑sort, merge‑sort) give O(n log n) time and need extra space or recursion. If the input already guarantees a one‑to‑one mapping between values and positions, you can do better: O(n) time and O(1) extra space. The pattern exploits that guarantee, turning the problem into a series of swaps rather than comparisons.

Signals That Call for Cyclic Sort

If you see any of these, pause and consider whether swapping each element to its rightful place will solve the problem.

Worked Example: Finding All Missing Numbers

Problem: Given an array nums of length n where each element is an integer in [1, n] (some numbers may be missing, some may appear twice), return all numbers that do not appear in the array.

Step‑by‑step solution:

1. Iterate through the array with an index i.
2. While nums[i] is not in its correct spot (nums[i] != i+1) and the target position does not already hold the same value, swap nums[i] with nums[nums[i]-1].
3. After the loop, any index i where nums[i] != i+1 indicates that i+1 is missing.

def find_missing(nums):
    i = 0
    n = len(nums)
    while i < n:
        correct = nums[i] - 1
        # Skip if already correct or duplicate would cause infinite loop
        if nums[i] != i + 1 and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    # Collect missing numbers
    missing = [i + 1 for i, v in enumerate(nums) if v != i + 1]
    return missing

Complexity: Each element is swapped at most once, so the loop runs O(n) times. No extra arrays are allocated beyond the result list, giving O(1) auxiliary space.

Common pitfalls:

• Forgetting the duplicate‑check (nums[i] != nums[correct]). Without it, the algorithm can loop forever when a number appears twice.
• Using 0‑based vs 1‑based indices incorrectly; the target index is value‑1.
• Modifying the input when the problem asks to preserve it. In that case, copy the array first (still O(1) extra space if you copy in‑place later).

Variations of the Pattern

While the core idea stays the same, you’ll see it applied to slightly different goals:

• Detect a single duplicate: after the cyclic sort, the index where nums[i] != i+1 gives the duplicate value.
• Find the smallest missing positive: similar to the missing‑numbers problem, but you stop after the first mismatch.
• Rearrange to "value equals index+1": sometimes the interview asks for the reordered array itself.

Five Practice Problems

Below are five problems that exercise the cyclic sort pattern. The descriptions avoid copying any copyrighted statements; each includes a hint that nudges you toward the right approach.

1. Missing Numbers (LeetCode‑like)

Prompt: An array of length n contains integers from 1 to n. Some numbers may be missing, others may appear twice. Return all missing numbers. Hint: Perform a cyclic sort so that each value lands at value‑1. After sorting, any index where the value is wrong reveals a missing number.

2. Find the Duplicate (Single Duplicate)

Prompt: An array of length n+1 contains integers from 1 to n. Exactly one value appears twice, the rest appear once. Return the duplicate. Hint: Use cyclic sort; the first index where nums[i] != i+1 after sorting holds the duplicate.

3. First Missing Positive

Prompt: Given an unsorted integer array, find the smallest positive integer that does not appear. Hint: Treat the array as if it should contain 1…n. Swap numbers into their correct slots only if they fall inside the range.

4. Sort Colors (0‑1‑2 variant)

Prompt: An array contains only 0, 1, and 2. Rearrange it so that all 0s come first, then 1s, then 2s. Hint: Although not a classic cyclic sort, you can map each color to its target region and swap in‑place. Think of three “buckets” and move elements to their bucket.

5. Array Restoration (Custom)

Prompt: You are given an array where each element is an integer from 1 to n but the array is shuffled. Return the array sorted without using any library sort. Hint: Directly apply cyclic sort; each value belongs at value‑1. No extra memory needed.

When Not to Use Cyclic Sort

• The range is not consecutive (e.g., numbers from 10 to 20). A hash‑based approach may be clearer.
• Duplicates are allowed and you need to preserve order; swapping may destroy required ordering.
• The problem explicitly asks for a stable sort; cyclic sort is unstable.
• Input size is tiny and readability matters more than optimal time.

How to Practice This

1. Write the core loop from memory – start with the while‑loop that swaps until each element is in place. Do it without looking at any reference.
2. Create edge‑case tests – include arrays with all numbers correct, all numbers reversed, a single duplicate, and numbers out of range. Run your code against them.
3. Explain aloud – use Call Assistant to rehearse your explanation as if you were in an interview. Keep the story concise (45‑90 seconds) and tie any personal project that involved data reordering to your answer.

---

FAQ

• Q: How does cyclic sort differ from counting sort? A: Counting sort builds a frequency table and then writes out the sorted values, using O(n) extra space. Cyclic sort rearranges the array in‑place by swapping, so it needs only O(1) additional space.
• Q: Can cyclic sort handle negative numbers? A: Only if you can map each negative to a valid index, which usually means the range must be contiguous and start at 0 or 1. Otherwise a different method is safer.
• Q: What if the array contains numbers outside the expected range? A: Skip those values during the swapping phase; they stay where they are and can be handled later (e.g., ignored for missing‑number problems).
• Q: Is cyclic sort stable? A: No. Swapping changes relative order, so if stability matters you need a different algorithm.