First Missing Positive

Problem Description

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Examples

Example 1:
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)
    
    # Step 1: Modify the array
    # Replace negative numbers, zero, and numbers larger than n with n+1
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1
    
    # Step 2: Mark the presence of each number in range [1,n]
    for i in range(n):
        num = abs(nums[i])
        if num <= n:
            nums[num - 1] = -abs(nums[num - 1])
    
    # Step 3: Find the first missing positive number
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    
    return n + 1

Java Solution


class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // Step 1: Modify the array
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        
        // Step 2: Mark presence of each number
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        
        // Step 3: Find first missing positive
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
}

C++ Solution


class Solution {
public:
    int firstMissingPositive(vector& nums) {
        int n = nums.size();
        
        // Step 1: Modify the array
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        
        // Step 2: Mark presence of each number
        for (int i = 0; i < n; i++) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        
        // Step 3: Find first missing positive
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const n = nums.length;
    
    // Step 1: Modify the array
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }
    
    // Step 2: Mark presence of each number
    for (let i = 0; i < n; i++) {
        const num = Math.abs(nums[i]);
        if (num <= n) {
            nums[num - 1] = -Math.abs(nums[num - 1]);
        }
    }
    
    // Step 3: Find first missing positive
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }
    
    return n + 1;
};

C# Solution


public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;
        
        // Step 1: Modify the array
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        
        // Step 2: Mark presence of each number
        for (int i = 0; i < n; i++) {
            int num = Math.Abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.Abs(nums[num - 1]);
            }
        }
        
        // Step 3: Find first missing positive
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the array
Space Complexity: O(1) as we modify the input array in-place

Solution Explanation

This solution uses array manipulation to solve the problem in O(n) time and O(1) space. Here's how it works:

Step 1: Modify the array
- Replace all numbers ≤ 0 or > n with n+1
- This ensures we only deal with positive numbers in range [1,n]
Step 2: Mark presence of numbers
- For each number i in range [1,n], mark its presence by making nums[i-1] negative
- Use absolute value to handle already negative numbers
Step 3: Find first missing
- First positive number in the array indicates missing index+1
- If all numbers are negative, return n+1

Key points:

Uses array indices as hash table
Negative numbers mark presence
Handles all edge cases
Maintains O(1) space complexity