Last updated on March 7th, 2025 at 10:04 pm

Here, we see the First Missing Positive LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Hash Table

Level of Question

Hard

First Missing Positive LeetCode Solution

1. Problem Statement

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

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.

2. Coding Pattern Used in Solution

The coding pattern used in the C++, Java, and JavaScript implementations is Cyclic Sort. This pattern is used when the problem involves rearranging elements in an array to their correct positions, typically when the array contains numbers in a specific range (e.g., 1 to n). The Python implementation, however, uses a Set-based Search pattern, which is different from the other three.

3. Code Implementation in Different Languages

3.1 First Missing Positive C++

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0 ; i<n ; i++)
        {
            while(nums[i]>0 and nums[i]<=n and nums[i]!=nums[nums[i]-1])
                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;      
    }
};

3.2 First Missing Positive Java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean[] exists = new boolean[n];
        for (int num : nums) {
            if (num > 0 && num <= n) exists[num - 1] = true;
        }
        for (int i = 0; i < exists.length; i++) {
            if (!exists[i]) return i + 1;
        }
        return n + 1;       
    }
}

3.3 First Missing Positive JavaScript

var firstMissingPositive = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        let idx = nums[i]-1;
        if (i == idx || nums[i] == nums[idx]) continue; 
        if (idx >= 0 && idx <= nums.length - 1) {
            [nums[i], nums[idx]] = [nums[idx], nums[i]];
            i--; 
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (i+1 == nums[i]) continue;
        else return i+1; 
    }
    return nums.length + 1; 
};

3.4 First Missing Positive Python

class Solution(object):
    def firstMissingPositive(self, nums):
        unique = set(nums)
        i = 1
        while i in unique:
            i += 1
        return i

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(n)
JavaScript	O(n)	O(1)
Python	O(n)	O(n)

• The C++, JavaScript, and Java implementations use the Cyclic Sort pattern, while the Python implementation uses a Set-based Search pattern.
• The C++ and JavaScript implementations are more space-efficient (O(1) space) compared to Java and Python (O(n) space).