First Missing Positive

LeetCode 41: First Missing Positive Solution & Explanation

Problem Overview

TL;DR: Use the Cyclic Sort pattern to place every positive integer $x$ at index $x-1$ in-place, then identify the first index that does not contain the correct value.

The First Missing Positive problem asks us to find the smallest positive integer (strictly greater than 0) that is absent from an unsorted array of integers. The critical constraints are that the solution must run in $O(n)$ time complexity and use $O(1)$ auxiliary space. This effectively rules out sorting algorithms (which are $O(n \log n)$) or using a Hash Set (which requires $O(n)$ space).

This is a popular interview question because it tests the ability to manipulate arrays in-place to extract information without extra memory allocation.

Brute Force Approach for First Missing Positive

A naive approach to solving LeetCode 41 involves using a Hash Set to track all positive integers present in the array. Once the set is populated, we can iterate starting from integer 1 and check if it exists in the set. The first integer not found in the set is our answer.

Alternatively, without extra space, one might sort the array first. After sorting, we can iterate through the array to find the first gap in the sequence of positive integers.

Pseudo-code (Sorting Approach):

function firstMissingPositive(nums):
    sort(nums)
    target = 1
    for num in nums:
        if num == target:
            target = target + 1
        elif num > target:
            return target
    return target

Why this fails:

1. Time Complexity: Sorting takes $O(n \log n)$, which violates the strict $O(n)$ time constraint provided in the problem statement.
2. Space Complexity: While the sorting approach can be $O(1)$ (depending on the sort implementation), the Hash Set approach mentioned initially would violate the $O(1)$ space constraint.

To satisfy both constraints simultaneously, we must utilize the input array itself as our storage mechanism.

Algorithm Strategy: Array - Cyclic Sort

The strategy utilizes the Cyclic Sort pattern to rearrange the array in $O(n)$ time using constant space.

1. Cyclic Swapping: Iterate through the array with an index pointer $i$. For each element nums[i]:

   • Check if the value is within the valid range $[1, n]$.
   • Check if the value is already at its correct index (i.e., does nums[i] equal nums[nums[i] - 1]?).
   • If the value is valid and misplaced, swap nums[i] with the element at the target index nums[i] - 1.
   • Crucially, after swapping, do not immediately advance the pointer $i$. The new value swapped into index $i$ might also be misplaced and need processing.
   • If the value is out of range or already correctly placed, advance $i$.

2. Verification Pass: Once the array is sorted cyclically:

   • Iterate through the array from index $0$ to $n-1$.
   • The first index $i$ where nums[i] != i + 1 reveals the answer. The missing number is $i + 1$.

3. Default Case: If all indices $0$ to $n-1$ contain the correct values $1$ to $n$, then the missing number is $n + 1$.

Execution Flow

Let's trace the algorithm with nums = [3, 4, -1, 1]. Length $n = 4$.

1. Index 0: nums[0] is 3.

   • Target index for 3 is 2 (3 - 1).
   • Is nums[0] != nums[2]? Yes ($3 \ne -1$).
   • Swap index 0 and 2.
   • Array becomes [-1, 4, 3, 1].
   • Re-evaluate Index 0: nums[0] is -1.
   • -1 is not in range $[1, 4]$. Ignore.
   • Advance to Index 1.

2. Index 1: nums[1] is 4.

   • Target index for 4 is 3 (4 - 1).
   • Is nums[1] != nums[3]? Yes ($4 \ne 1$).
   • Swap index 1 and 3.
   • Array becomes [-1, 1, 3, 4].
   • Re-evaluate Index 1: nums[1] is 1.
   • Target index for 1 is 0 (1 - 1).
   • Is nums[1] != nums[0]? Yes ($1 \ne -1$).
   • Swap index 1 and 0.
   • Array becomes [1, -1, 3, 4].
   • Re-evaluate Index 1: nums[1] is -1.
   • -1 is not in range $[1, 4]$. Ignore.
   • Advance to Index 2.

3. Index 2: nums[2] is 3.

   • Target index for 3 is 2.
   • It is already at the correct index ($3 == 3$).
   • Advance to Index 3.

4. Index 3: nums[3] is 4.

   • Target index for 4 is 3.
   • It is already at the correct index ($4 == 4$).
   • End of loop.

5. Final Scan:

   • Check nums[0]: Is $1 == 0 + 1$? Yes.
   • Check nums[1]: Is $-1 == 1 + 1$? No.
   • Return $1 + 1 = 2$.

Proof of Correctness

The algorithm is correct because it attempts to enforce the invariant nums[i] == i + 1 for all valid positive integers $x$ where $1 \le x \le n$.

• If a number $x$ exists in the input and $1 \le x \le n$, the cyclic sort guarantees it will be moved to index $x-1$.
• The condition nums[i] != nums[nums[i] - 1] handles duplicates safely (preventing infinite swaps) and ensures we only swap if it puts the number in the correct position.
• By iterating sequentially after sorting, the first index $i$ that fails the check nums[i] == i + 1 implies that the number $i+1$ was not present in the original array to fill that slot.

Pattern Reuse Notes

The Array - Cyclic Sort pattern used in LeetCode 41 is a powerful technique for problems involving arrays containing numbers in a specific range (usually $0$ to $n$ or $1$ to $n$).

• LeetCode 268: Missing Number: Very similar, but the range is $0$ to $n$. The logic is identical: place $x$ at index $x$.
• LeetCode 287: Find the Duplicate Number: Uses the cycle detection aspect of this pattern (or Floyd's Tortoise and Hare) to find the duplicate without modifying the array (if modification is restricted) or by cyclic sorting.
• LeetCode 442: Find All Duplicates in an Array: Instead of sorting, we can negate the value at the target index to mark it as visited.
• LeetCode 448: Find All Numbers Disappeared in an Array: Identical to finding the missing positive, but we collect all indices where the value is incorrect rather than just the first one.

Reference Implementation

C++ Solution for LeetCode 41

1class Solution {
2public:
3    int firstMissingPositive(vector<int>& nums) {
4        int n = nums.size();
5        
6        // Cyclic Sort: Place each number x at index x - 1
7        for (int i = 0; i < n; ++i) {
8            // While nums[i] is in range [1, n] and not at the correct position
9            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
10                // Swap nums[i] to its correct position nums[i] - 1
11                swap(nums[i], nums[nums[i] - 1]);
12            }
13        }
14        
15        // Find the first index where the index doesn't match the value
16        for (int i = 0; i < n; ++i) {
17            if (nums[i] != i + 1) {
18                return i + 1;
19            }
20        }
21        
22        // If all positions are correct, the missing number is n + 1
23        return n + 1;
24    }
25};

Java Solution for LeetCode 41

1class Solution {
2    public int firstMissingPositive(int[] nums) {
3        int n = nums.length;
4        int i = 0;
5        
6        // Cyclic Sort
7        while (i < n) {
8            int correctIndex = nums[i] - 1;
9            // Check if nums[i] is in range [1, n] and needs to be moved
10            if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
11                swap(nums, i, correctIndex);
12            } else {
13                i++;
14            }
15        }
16        
17        // Scan for the first missing positive
18        for (int j = 0; j < n; j++) {
19            if (nums[j] != j + 1) {
20                return j + 1;
21            }
22        }
23        
24        return n + 1;
25    }
26    
27    private void swap(int[] nums, int i, int j) {
28        int temp = nums[i];
29        nums[i] = nums[j];
30        nums[j] = temp;
31    }
32}

Python Solution for LeetCode 41

1class Solution:
2    def firstMissingPositive(self, nums: List[int]) -> int:
3        n = len(nums)
4        i = 0
5        
6        # Cyclic Sort
7        while i < n:
8            correct_index = nums[i] - 1
9            # Check if nums[i] is in range [1, n] and at the wrong position
10            if 0 < nums[i] <= n and nums[i] != nums[correct_index]:
11                # Swap elements
12                nums[correct_index], nums[i] = nums[i], nums[correct_index]
13            else:
14                # Only advance if we didn't swap or if current number is irrelevant
15                i += 1
16                
17        # Find the first index mismatch
18        for i in range(n):
19            if nums[i] != i + 1:
20                return i + 1
21                
22        return n + 1