Autocoder

Cyclic sort pattern interview questions with worked solutions

Last updated 2026-11-19

Cyclic sort is for arrays that hold numbers in a known range, typically 1 to n or 0 to n. If value v belongs at index v - 1, you can put every number in its place by swapping, using O(1) extra space and O(n) time. Afterwards, any index that holds the wrong number reveals a missing or duplicate value.

The trigger is a statement such as "the array has n numbers in the range 1 to n" or "find the missing, duplicate or smallest missing positive number in O(1) space". The ten problems below use the same loop with small variations. For the general in-place array toolkit see arrays questions, and for the hash-based alternative that uses extra space see hashing questions.

Problems10, easy to hard
LanguagesPython and Java
Applies whenValues are in 1..n or 0..n

The loop

Use an index i. The correct position of a[i] is j = a[i] - 1. If a[i] is already at j (or the same value is there, meaning a duplicate), advance i. Otherwise swap a[i] with a[j] and do not advance, because the value that arrived at i has not been placed yet.

The while loop is still linear: every swap puts one number into its final place, so there are at most n swaps. The array is modified, so say so to the interviewer, and if the original must be kept, work on a copy or use the negation-marking alternative.

What the finished array tells you

After sorting, scan for indices where a[i] is not i + 1. The index gives the missing number (i + 1) and the value sitting there is a duplicate or an out-of-range number. That is the basis for every problem below.

Cyclic sort pattern interview questions with worked solutions: questions with worked answers

  1. 1

    Cyclic sort: sort an array containing the numbers 1 to n exactly once.

    easy

    For each position, send the value to its home index value - 1 by swapping, and only advance when the current value is already home. For [3,1,2]: swap index 0 with index 2 giving [2,1,3], swap index 0 with index 1 giving [1,2,3]. This sorts in linear time because each swap fixes one value permanently. Time O(n), space O(1).. Edge cases: already sorted, reverse order, a single element.

    python
    def cyclic_sort(a):
        i = 0
        while i < len(a):
            j = a[i] - 1
            if a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        return a
    java
    import java.util.*;
    
    class Solution {
        static void cyclicSort(int[] a) {
            int i = 0;
            while (i < a.length) {
                int j = a[i] - 1;
                if (a[i] != a[j]) {
                    int t = a[i]; a[i] = a[j]; a[j] = t;
                } else i++;
            }
        }
    }
  2. 2

    Is the array a permutation of 1 to n?

    easy

    First reject any value outside 1..n. Then run the cyclic placement; if the array is a permutation, every value lands in its own slot. Finally check that a[i] equals i + 1 everywhere. A duplicate leaves some value out of place, because its slot is already taken. Time O(n), space O(1) (the array is modified).. Edge cases: a value of 0 or above n, one duplicate, an empty array.

    python
    def is_permutation(a):
        n = len(a)
        if any(x < 1 or x > n for x in a):
            return False
        i = 0
        while i < n:
            j = a[i] - 1
            if a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        return all(a[i] == i + 1 for i in range(n))
    java
    import java.util.*;
    
    class Solution {
        static boolean isPermutation(int[] a) {
            int n = a.length;
            for (int x : a) if (x < 1 || x > n) return false;
            int i = 0;
            while (i < n) {
                int j = a[i] - 1;
                if (a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            for (i = 0; i < n; i++) if (a[i] != i + 1) return false;
            return true;
        }
    }
  3. 3

    Missing number: an array holds n distinct numbers from 0 to n; find the missing one.

    easy

    Place each value v at index v when v is less than n (n has no slot, so leave it). Afterwards the first index where a[i] differs from i is the missing number; if every index matches, the missing number is n. Using XOR or the sum formula needs no mutation, but this shows the pattern for the harder variants. Time O(n), space O(1).. Edge cases: missing 0, missing n (all indices match), one element.

    python
    def missing_number(a):
        n = len(a)
        i = 0
        while i < n:
            j = a[i]
            if j < n and a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        for i in range(n):
            if a[i] != i:
                return i
        return n
    java
    import java.util.*;
    
    class Solution {
        static int missingNumber(int[] a) {
            int n = a.length, i = 0;
            while (i < n) {
                int j = a[i];
                if (j < n && a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            for (i = 0; i < n; i++) if (a[i] != i) return i;
            return n;
        }
    }
  4. 4

    Find all numbers from 1 to n that are missing from an array of n values (duplicates allowed).

    medium

    Run cyclic placement. Duplicates cannot all be placed, so some indices keep the wrong value. Each index i where a[i] is not i + 1 means that i + 1 is missing from the input. Collect those. Time O(n), space O(1) beyond the output.. Edge cases: all numbers present (empty list), every element equal, a single element.

    python
    def find_disappeared(a):
        i = 0
        while i < len(a):
            j = a[i] - 1
            if a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        return [i + 1 for i in range(len(a)) if a[i] != i + 1]
    java
    import java.util.*;
    
    class Solution {
        static List<Integer> findDisappeared(int[] a) {
            int i = 0;
            while (i < a.length) {
                int j = a[i] - 1;
                if (a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            List<Integer> res = new ArrayList<>();
            for (i = 0; i < a.length; i++) if (a[i] != i + 1) res.add(i + 1);
            return res;
        }
    }
  5. 5

    Find the duplicate number in an array of n + 1 values from 1 to n (exactly one value repeats, possibly several times).

    medium

    Run the placement loop. When a[i] is not at its home index and the home slot already holds the same value, that value is the duplicate: return it. Otherwise swap. Because n + 1 values compete for n slots, a clash must occur. If you cannot modify the array, use fast and slow pointers instead. Time O(n), space O(1) (the array is modified).. Edge cases: the duplicate repeated many times, duplicate at the start or end, n = 1 ([1, 1]).

    python
    def find_duplicate(a):
        i = 0
        while i < len(a):
            if a[i] != i + 1:
                j = a[i] - 1
                if a[i] != a[j]:
                    a[i], a[j] = a[j], a[i]
                else:
                    return a[i]
            else:
                i += 1
        return -1
    java
    import java.util.*;
    
    class Solution {
        static int findDuplicate(int[] a) {
            int i = 0;
            while (i < a.length) {
                if (a[i] != i + 1) {
                    int j = a[i] - 1;
                    if (a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                    else return a[i];
                } else i++;
            }
            return -1;
        }
    }
  6. 6

    Find all duplicates in an array of n numbers in 1..n where each number appears once or twice.

    medium

    After cyclic placement, every index holding a value other than i + 1 holds a number that appeared twice, because the second copy could not find an empty home. Collect those a[i] values. Alternatively, mark visited values by negating the value at their home index without moving anything. Time O(n), space O(1) beyond the output.. Edge cases: no duplicates (empty list), all numbers duplicated in pairs, n = 1.

    python
    def find_duplicates(a):
        i = 0
        while i < len(a):
            j = a[i] - 1
            if a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        return [a[i] for i in range(len(a)) if a[i] != i + 1]
    java
    import java.util.*;
    
    class Solution {
        static List<Integer> findDuplicates(int[] a) {
            int i = 0;
            while (i < a.length) {
                int j = a[i] - 1;
                if (a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            List<Integer> res = new ArrayList<>();
            for (i = 0; i < a.length; i++) if (a[i] != i + 1) res.add(a[i]);
            return res;
        }
    }
  7. 7

    Set mismatch: one number in 1..n was duplicated and another became missing; find both.

    medium

    After cyclic placement exactly one index holds the wrong value. The value stored there is the duplicate, and the index plus one is the missing number. For [1,2,2,4] the answer is duplicate 2 and missing 3. Time O(n), space O(1).. Edge cases: missing number is 1, duplicate sits at the end, n = 2 ([1, 1]).

    python
    def find_error_nums(a):
        i = 0
        while i < len(a):
            j = a[i] - 1
            if a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        for i in range(len(a)):
            if a[i] != i + 1:
                return [a[i], i + 1]
        return [-1, -1]
    java
    import java.util.*;
    
    class Solution {
        static int[] findErrorNums(int[] a) {
            int i = 0;
            while (i < a.length) {
                int j = a[i] - 1;
                if (a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            for (i = 0; i < a.length; i++)
                if (a[i] != i + 1) return new int[]{a[i], i + 1};
            return new int[]{-1, -1};
        }
    }
  8. 8

    Minimum swaps to sort a permutation of 1..n.

    medium

    Count the swaps cyclic sort performs. Each swap puts exactly one element in its final place, and a permutation decomposes into cycles: a cycle of length c needs c - 1 swaps, so the total is n minus the number of cycles. Counting swaps in the placement loop gives that number directly. Time O(n), space O(1).. Edge cases: already sorted (0), one big cycle (n - 1), only 2-cycles.

    python
    def min_swaps(a):
        a = a[:]
        i = swaps = 0
        while i < len(a):
            j = a[i] - 1
            if j != i:
                a[i], a[j] = a[j], a[i]
                swaps += 1
            else:
                i += 1
        return swaps
    java
    import java.util.*;
    
    class Solution {
        static int minSwaps(int[] input) {
            int[] a = input.clone();
            int i = 0, swaps = 0;
            while (i < a.length) {
                int j = a[i] - 1;
                if (j != i) {
                    int t = a[i]; a[i] = a[j]; a[j] = t;
                    swaps++;
                } else i++;
            }
            return swaps;
        }
    }
  9. 9

    First missing positive integer in O(n) time and O(1) space.

    hard

    Only values in 1..n can matter, because among n numbers the smallest missing positive is at most n + 1. Place each value in 1..n at index value - 1, ignoring zeroes, negatives and large values. The first index where a[i] is not i + 1 gives the answer i + 1; if all match, the answer is n + 1. Time O(n), space O(1).. Edge cases: all negatives (1), a perfect run [1..n] (n + 1), duplicates that must not cause an infinite loop.

    python
    def first_missing_positive(a):
        n = len(a)
        i = 0
        while i < n:
            j = a[i] - 1
            if 0 <= j < n and a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        for i in range(n):
            if a[i] != i + 1:
                return i + 1
        return n + 1
    java
    import java.util.*;
    
    class Solution {
        static int firstMissingPositive(int[] a) {
            int n = a.length, i = 0;
            while (i < n) {
                int j = a[i] - 1;
                if (j >= 0 && j < n && a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            for (i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
            return n + 1;
        }
    }
  10. 10

    Find the first K missing positive numbers.

    hard

    Place values in 1..n as before. Scan the array: each index with the wrong value yields a missing number i + 1, and the misplaced value there is recorded in a set because it could otherwise be mistaken for a missing candidate beyond n. If fewer than K were found, continue counting upwards from n + 1, skipping any number in that set. Time O(n + K), space O(K) for the set and the result.. Edge cases: K larger than the number of gaps below n, negative or zero values, duplicates occupying wrong slots.

    python
    def first_k_missing(a, k):
        n = len(a)
        i = 0
        while i < n:
            j = a[i] - 1
            if 0 <= j < n and a[i] != a[j]:
                a[i], a[j] = a[j], a[i]
            else:
                i += 1
        res, extra = [], set()
        for i in range(n):
            if len(res) < k and a[i] != i + 1:
                res.append(i + 1)
                extra.add(a[i])
        c = n + 1
        while len(res) < k:
            if c not in extra:
                res.append(c)
            c += 1
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<Integer> firstKMissing(int[] a, int k) {
            int n = a.length, i = 0;
            while (i < n) {
                int j = a[i] - 1;
                if (j >= 0 && j < n && a[i] != a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
                else i++;
            }
            List<Integer> res = new ArrayList<>();
            Set<Integer> extra = new HashSet<>();
            for (i = 0; i < n; i++) {
                if (res.size() < k && a[i] != i + 1) {
                    res.add(i + 1);
                    extra.add(a[i]);
                }
            }
            for (int c = n + 1; res.size() < k; c++)
                if (!extra.contains(c)) res.add(c);
            return res;
        }
    }
  11. 11

    Why does the cyclic sort loop run in linear time even though it has a nested-looking while loop, and when does it fail to terminate?

    hard

    Each swap places one value at its home index, where it stays, so at most n swaps can ever happen; every other iteration advances i. The loop only fails to terminate if you swap two equal values (a duplicate) and never advance. The guard a[i] != a[j] prevents that by advancing when the target slot already holds the same value. Out-of-range values must also skip the swap, or the index would be invalid.

Frequently asked questions

When can I use cyclic sort?

When the numbers are within a known range tied to the array length, such as 1..n or 0..n. If values can be arbitrary, use hashing or sorting instead.

Does cyclic sort modify the input?

Yes, it rearranges the array in place. If you must preserve it, copy the array first (costing O(n) space) or use negation marking, which flips signs and can be undone.

Why do I not advance i after a swap?

The value that arrived at index i has not been placed yet, so it must be examined again. Only advance when the current value is at its home index or a duplicate already occupies that home.

What if the range is 0 to n?

Place value v at index v when v is less than n. The value n has no home slot and is ignored. The first index with the wrong value is the missing number, or n if all match.

How is this different from counting sort?

Counting sort needs O(k) extra space for a count array. Cyclic sort uses the array itself as the table, which only works when the range matches the length.

Related guides

More in DSA Interview Questions

See all in this section