Cyclic Sort

Concept

Sorting an array mathematically requires $O(N \log N)$ time (Merge Sort, Quick Sort).

However, there is a very specific, heavily-tested interview pattern:
“You are given an unsorted array of size N containing numbers from 1 to N. Find the missing/duplicate number.”

Whenever a problem explicitly states the numbers are in a strict, continuous range from 1 to N (or 0 to N), you can sort the entire array in blazing fast $O(N)$ time using the Cyclic Sort pattern.

The Mental Model

If an array has 5 slots, and the numbers are exactly 1 through 5, then there is only one mathematically correct sorted state:
The number 1 belongs at Index 0.
The number 2 belongs at Index 1.
The number 5 belongs at Index 4.

The Rule: Number belongs at Index = Number - 1.

Instead of using complex pivot logic like Quick Sort, we just iterate through the array. If the number we are looking at is not sitting in its correct mathematical index, we physically pick it up and swap it into its correct index. We repeat this until every number is in the right seat.

Implementation

// Time Complexity: O(N)
// Space Complexity: O(1) (In-place swaps)
function cyclicSort(nums: number[]): void {
    let i = 0;
    
    while (i < nums.length) {
        // Where does this number mathematically belong?
        // E.g., if nums[i] is 3, it belongs at index 2.
        const correctIndex = nums[i] - 1;

        // Is it already in the correct spot? (And is it within bounds?)
        if (nums[i] > 0 && nums[i] <= nums.length && nums[i] !== nums[correctIndex]) {
            // No! Swap it to where it belongs.
            // Notice we DO NOT increment 'i'. The new number that just swapped 
            // into 'i' also needs to be evaluated!
            let temp = nums[i];
            nums[i] = nums[correctIndex];
            nums[correctIndex] = temp;
        } else {
            // Yes! It's in the right spot (or it's an out-of-bounds number). 
            // Move on to the next index.
            i++;
        }
    }
}

Why is this $O(N)$ if there’s a while loop that doesn’t always increment?

It looks like it could run infinitely, but it can’t. Every single time a swap happens, at least one number is placed permanently into its mathematically correct, final resting index. Because there are only $N$ numbers, the absolute maximum number of swaps that can physically occur across the entire execution is $N$. Therefore, the total time is $O(N) + O(N) = O(N)$.

Finding the Missing/Duplicate Number

Once the array is sorted using Cyclic Sort, finding the answer to the interview question is trivial. You just do one final $O(N)$ loop.

Problem: Find the missing number.

// After running Cyclic Sort...
// Expected: [1, 2, 3, 4]
// Actual:   [1, 2, 4, 5] (Wait, index 2 has the number 4?)
for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
        return i + 1; // The mathematical number that SHOULD be here is missing!
    }
}

Interview Questions

Q: A classic problem is “Find the Missing Number in an array containing 0 to N”. Can you solve this without Cyclic Sort?
A: Yes, there is a famous $O(N)$ time, $O(1)$ space mathematical trick for this specific problem using Gauss’s Formula.
If $N=5$, the expected mathematical sum of the array is 5 * (5 + 1) / 2 = 15.
You loop through the array once and sum up the actual numbers (e.g., 12).
The missing number is simply ExpectedSum - ActualSum (15 - 12 = 3).
(Note: While Gauss’s formula is cleaner, Cyclic Sort is required when the array has MULTIPLE missing or duplicate numbers, which Gauss’s formula cannot handle).

Q: The problem “Find All Duplicates in an Array” explicitly asks for an $O(N)$ runtime and $O(1)$ extra space. You could use Cyclic Sort, but is there another $O(1)$ space trick?
A: Yes, the State Mapping (Index Negation) trick.
Because the numbers are strictly 1 to N, you can use the values themselves as pointers to array indices.
As you iterate through the array, you look at abs(nums[i]). You go to that index, and multiply the value sitting there by -1.
If you ever go to an index and the value is already negative, it means you have seen this number before! You found a duplicate, and you did it in $O(N)$ time with strictly $O(1)$ space.