First Missing Positive

41.First Missing Positive

Array

Bit Manipulation

Problem Statement:

Given an unsorted integer array nums, find the smallest missing positive integer. Must run in O(n) time and use constant extra space.

Example:

Input:

nums = [3,4,-1,1]

→

Output:

2

Algorithm:

1. Place each number at its correct index (num at index num-1)
2. Skip invalid numbers (≤0, >length, or already correct)
3. Check for infinite loop when swapping equal numbers
4. Find first position where number doesn't match index+1

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public int firstMissingPositive(int[] nums) {
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] <= 0 || nums[i] == i + 1 || nums[i] > nums.length) continue;
        // Check if numbers are same to prevent infinite loop
        if (nums[nums[i] - 1] != nums[i]) {
            swap(nums, nums[i] - 1, i);
            i--;  // Process swapped number
        }
    }
    
    for (int i = 0; i < nums.length; i++) 
        if (nums[i] != i + 1) 
            return i + 1;
    
    return nums.length + 1;
}

public void swap(int[] nums, int a, int b) {
    nums[a] ^= nums[b];
    nums[b] ^= nums[a];
    nums[a] ^= nums[b];
}

Python Solution:

def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)
    i = 0
    
    while i < n:
        if nums[i] <= 0 or nums[i] == i + 1 or nums[i] > n:
            i += 1
            continue
        
        correct_pos = nums[i] - 1
        if nums[correct_pos] != nums[i]:
            nums[correct_pos], nums[i] = nums[i], nums[correct_pos]
        else:
            i += 1
    
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
            
    return n + 1

C++ Solution:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        for(int i = 0; i < n; i++) {
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        
        for(int i = 0; i < n; i++) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};