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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Applies when | Values 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.
- Range 1..n: correct index is value - 1.
- Range 0..n: correct index is the value itself, and n has no slot, so skip it.
- Duplicates: when the target slot already holds the same value, advance to avoid an infinite loop.
- Out-of-range values (zero, negatives, large): ignore them in the swap condition.
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 Cyclic sort: sort an array containing the numbers 1 to n exactly once.
easyFor 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.
pythondef 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 ajavaimport 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 Is the array a permutation of 1 to n?
easyFirst 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.
pythondef 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))javaimport 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 Missing number: an array holds n distinct numbers from 0 to n; find the missing one.
easyPlace 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.
pythondef 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 njavaimport 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 Find all numbers from 1 to n that are missing from an array of n values (duplicates allowed).
mediumRun 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.
pythondef 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]javaimport 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 Find the duplicate number in an array of n + 1 values from 1 to n (exactly one value repeats, possibly several times).
mediumRun 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]).
pythondef 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 -1javaimport 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 Find all duplicates in an array of n numbers in 1..n where each number appears once or twice.
mediumAfter 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.
pythondef 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]javaimport 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 Set mismatch: one number in 1..n was duplicated and another became missing; find both.
mediumAfter 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]).
pythondef 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]javaimport 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 Minimum swaps to sort a permutation of 1..n.
mediumCount 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.
pythondef 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 swapsjavaimport 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 First missing positive integer in O(n) time and O(1) space.
hardOnly 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.
pythondef 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 + 1javaimport 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 Find the first K missing positive numbers.
hardPlace 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.
pythondef 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 resjavaimport 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 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?
hardEach 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
- Array interview questions with worked solutions
- Hashing interview questions with worked solutions
- Fast and slow pointers interview questions with solutions
- Bit manipulation interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Math and number theory interview questions with solutions
More in DSA Interview Questions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions