Cyclic sort

Clue: numbers from 0 to n (or 1 to n) in an array of about n seats. Worked example: LeetCode 268, Missing Number (Easy). nums holds n distinct numbers from the range 0 to n; return the one number from that range that is missing.

The idea

Cinema seats: tickets 0 to 5, but only seats 0 to 4. Value v belongs in seat (index) v. Wrong seat? Swap into yours; whoever was there gets your old seat. Ticket 5? There is no seat 5, so stay where you are and move to the next person. Only after all the swaps, check every seat: the first seat i that does not hold i is the missing number. If every seat matches, the missing number is n.

The walk

[3, 0, 4, 1, 5] becomes [0, 1, 5, 3, 4] after 3 swaps and 1 skip. Every number with a seat ends up in it. Seat 2 holds 5, not 2, so the answer is 2.

Quick check from the post: [1, 2, 0] becomes [0, 1, 2]. Seats 0, 1 and 2 all match, so no seat is wrong and the missing number is n = 3.

Pseudocode

function missingNumber(nums):
    n = length(nums)
    i = 0
    while i < n:
        seat = nums[i]
        if seat < n and nums[seat] != seat:
            swap nums[i], nums[seat]
        else:
            i = i + 1          // home, or no seat
    for i from 0 to n - 1:
        if nums[i] != i:       // wrong number
            return i
    return n

The trap: the number 5 has no seat. Check seat < n first. Without that check, on [3, 0, 4, 1, 5] the code looks up nums[5], a seat that doesn't exist, and crashes. With it, 5 is skipped and the scan finds seat 2.

Code

public class Main {
    static int missingNumber(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int seat = nums[i];
            if (seat < n && nums[seat] != seat) {
                int tmp = nums[i];
                nums[i] = nums[seat];
                nums[seat] = tmp;
            } else {
                i = i + 1;
            }
        }
        for (i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

def missing_number(nums):
    n = len(nums)
    i = 0
    while i < n:
        seat = nums[i]
        if seat < n and nums[seat] != seat:
            nums[i], nums[seat] = nums[seat], nums[i]
        else:
            i = i + 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n

#include <bits/stdc++.h>
using namespace std;

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int seat = nums[i];
        if (seat < n && nums[seat] != seat) {
            swap(nums[i], nums[seat]);
        } else {
            i = i + 1;
        }
    }
    for (i = 0; i < n; i++) {
        if (nums[i] != i) return i;
    }
    return n;
}

function missingNumber(nums) {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        const seat = nums[i];
        if (seat < n && nums[seat] !== seat) {
            [nums[i], nums[seat]] = [nums[seat], nums[i]];
        } else {
            i = i + 1;
        }
    }
    for (i = 0; i < n; i++) {
        if (nums[i] !== i) return i;
    }
    return n;
}

Complexity

• Time: O(n). Every swap puts one number in its own seat for good, so there are at most n swaps, plus one scan.
• Extra space: O(1). The swaps happen inside nums (note: this reorders the input array).

How it was tested

All four agree with a brute-force check on 2,014 cases (2,000 random arrays with n from 1 to 12, plus edge cases: single element, missing 0, missing n, reversed, and three arrays at the maximum size n = 10,000). Re-run on 31 October 2026 on 3,004 more cases (3,000 random arrays with n from 1 to 12, the example, the quick check, [0] and [1]): all four matched on every one.