Cyclic Sort
When numbers are in range [1, N], each number belongs at index (number - 1). Swap each number to its correct position in O(n).
Time
O(n)
Space
O(1)
Recognize it when
- Array of N numbers in range [1, N]
- Find missing or duplicate numbers
- Find the smallest missing positive
Questions — ordered by difficulty
Missing Number
Given an array nums of n distinct numbers in the range [0, n], find and return the one number that is missing. Example: [3,0,1] → 2 (range is 0–3, the number 2 is absent). Two approaches: Gauss formula (sum trick) or XOR — both O(1) space.
Find All Numbers Disappeared in an Array
Given an array nums of n integers where each element is in the range [1, n], some elements appear twice and some appear once. Find all the integers in [1, n] that do not appear in nums. Example: [4,3,2,7,8,2,3,1] → [5,6]. Must be O(n) time and O(1) extra space (the output doesn't count).
Find the Duplicate Number (Cyclic Sort approach)
Given an array of n+1 integers where each integer is in the range [1, n], find the duplicate number. You must not modify the array and must use O(1) extra space. The cyclic-sort approach leverages the fact that each number belongs at a specific index.
First Missing Positive
Find the smallest missing positive integer in an unsorted array. Must be O(n) time and O(1) space.