Cyclic SortMediumO(n) time · O(1) space

Find the Smallest Missing Positive Number

Mahabharata — The First Gap — The Lowest Rank Absent from the Pandava Ranks

धनात्मकेषु संख्यासु लघुतमः अनुपस्थितः कः?। क्रमेण गणयित्वा प्रथमं अभावं ज्ञातव्यम्॥

*Among the positive numbers, which smallest one is absent? Count in order — find the first gap.*

The Story

Given an unsorted integer array (may contain negatives, zeros, large positives, duplicates), find the smallest missing positive integer.

For `nums = [3,4,-1,1]`, the answer is 2. For `nums = [1,2,0]`, the answer is 3. For `nums = [7,8,9,11,12]`, the answer is 1.

**Key insight:** The answer must be in the range [1, n+1]. Why? Even if the array contains 1, 2, ..., n (perfect), the answer would be n+1. With any missing number, the answer is ≤ n.

**Cyclic sort strategy:** Ignore numbers outside [1, n]. Place each valid number x at index x-1. After sort, find the first index where nums[i] ≠ i+1. That i+1 is the answer.

Modified cyclic sort: ``` while i < n: correct = nums[i] - 1 if 1 <= nums[i] <= n AND nums[i] != nums[correct]: swap(nums, i, correct) else: i++ ```

For `[3,4,-1,1]`: - i=0: nums[0]=3, correct=2. 1<=3<=4 and 3≠nums[2]=-1 → swap → [-1,4,3,1] - i=0: nums[0]=-1. Not in [1,4] → i++ - i=1: nums[1]=4, correct=3. swap → [-1,1,3,4] - i=1: nums[1]=1, correct=0. swap → [1,-1,3,4] - i=1: nums[1]=-1. skip → i++ - i=2: nums[2]=3, correct=2. match → i++ - i=3: nums[3]=4, correct=3. match → i++ Result: [1,-1,3,4]

Scan: i=0: 1=1 ✓. i=1: -1≠2 → return 2 ✓

This is O(n) time, O(1) space — the optimal solution to what appears to be a hard problem.

The Naive Counter

Try 1, 2, 3, ... checking if each is in the array (using a HashSet). O(n) time, O(n) space.

java

public int firstMissingPositiveBruteForce(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    for (int i = 1; ; i++)
        if (!set.contains(i)) return i;
}

The Cyclic Sort Wisdom

Only numbers in [1,n] have valid indices. Place valid x at index x-1, ignore others. After sort, first index i with nums[i]≠i+1 gives the answer i+1. If all correct, answer is n+1.

java

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    int i = 0;
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[correct]) {
            int temp = nums[i]; nums[i] = nums[correct]; nums[correct] = temp;
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++)
        if (nums[j] != j + 1) return j + 1;
    return n + 1;
}

Step-by-Step Walkthrough

nums=[3,4,-1,1]
Cyclic sort → [1,-1,3,4]
Scan: i=0: 1=1✓. i=1: -1≠2 → return 2 ✅

Deep Insight

**Why the answer is in [1, n+1]?** With n elements, there are at most n distinct positive integers. The pigeonhole principle guarantees that at least one positive integer in [1, n+1] is absent.

**Handling numbers outside [1,n]:** Negatives, zeros, and numbers >n are irrelevant — they can't fill any of the required positive positions 1..n. We simply skip them during cyclic sort.

**The `nums[i] != nums[correct]` check:** Prevents infinite loops when there are duplicates (e.g., [1,1]). If nums[i] already equals nums[correct], swapping would do nothing — both positions have the same value.

**This is LeetCode Hard** — yet the cyclic sort approach makes it surprisingly clean.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(n)	HashSet for existence check
Optimal	O(n)	O(1)	In-place cyclic sort + scan

Pattern Recognition

✅ Smallest missing positive in unsorted array
✅ Answer is in [1, n+1]
✅ Cyclic sort: only place valid numbers (1..n)
✅ Skip: negatives, zeros, >n, duplicates

**LeetCode Trigger Phrases:**
→ "first missing positive"
→ "smallest missing positive integer"
→ "O(1) space" + missing positive

Bhagavad Gita 9.3

अश्रद्दधानाः पुरुषा धर्मस्यास्य परन्तप। अप्राप्य मां निवर्तन्ते मृत्युसंसारवर्त्मनि॥

Those without faith in this dharma, O Parantapa, not attaining Me, return to the path of mortal existence.

Connection: The first missing positive is the first dharmic position left unfulfilled — the smallest gap in the sequence of proper order. Like the soul that doesn't attain liberation and must return to fill its cosmic role, the algorithm searches for the first unfulfilled position. Numbers outside [1,n] are like souls not yet ready for their rightful place — they are noted but passed over, as the algorithm focuses only on those eligible for dharmic placement.