Problem Statement: First Missing Positive

Description:

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

some top tech companies that have asked the "First Missing Positive" problem in their interviews

Example 1:

Input: nums = [1,2,0]
Output = 3

Example 2:

Input: nums = [3,4,-1,1]
Output = 2

Example 3:

Input: nums = [7,8,9,11,12]
Output = 1

Constraints

• n == nums.length
• 1 <= n <= 10^3.
• -10^2 <= nums[i] <= 10^2.

Output Format

Return a integer value

Now try it yourself
.
.
.
.
.
.
.
.
.
.
.
.
.

Solution in C:

#include<stdio.h>

int firstMissingPositive(int nums[], int n){

    // Insertion sort the array
    for(int i = 1; i < n; i++){
        int key = nums[i];
        int j = i - 1; 
        while(j >= 0 && nums[j] > key){ 
            nums[j + 1] = nums[j];
            j = j--; 
        } 
        nums[j + 1] = key; 
    } 
        
    // After sorting, find the first missing positive
    
    int smallestMissing = 1;    // consider the smallest missing

    for(int i = 0; i < n; i++){ 
       if (nums[i] == smallestMissing){ 
          smallestMissing++; 
        } 
    } 

    return smallestMissing;
}

void main(){
    int nums[] = {7,8,9,11,12};
    int n = 5;
    int answer = firstMissingPositive(nums, n);
}

Solution in C++:

#include<bits/stdc++.h>
using namespace std;

int firstMissingPositive(int nums[], int n){

    // Insertion sort the array
    for(int i = 1; i < n; i++){
        int key = nums[i];
        int j = i - 1; 
        while(j >= 0 && nums[j] > key){ 
            nums[j + 1] = nums[j];
            j = j--; 
        } 
        nums[j + 1] = key; 
    } 
        
    // After sorting, find the first missing positive
    
    int smallestMissing = 1;    // consider the smallest missing

    for(int i = 0; i < n; i++){ 
       if (nums[i] == smallestMissing){ 
          smallestMissing++; 
        } 
    } 

    return smallestMissing;
}

int main(){
    int nums[] = {7,8,9,11,12};
    cout<<"The first smallest positive number which is missing from the array is : ";
    cout<<firstMissingPositive(nums, 5); // 5 is the size of the array
}

Solution in Java:

class Solution{

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // Insertion sort the array
        for(int i = 1; i < n; i++){
            int key = nums[i]; 
            int j = i - 1; 
            while(j >= 0 && nums[j] > key){ 
                nums[j + 1] = nums[j]; 
                j = j--; 
                
            } 
            nums[j + 1] = key; 
            
        } 
        
        // After sorting, find the first missing positive 
        
        int smallestMissing = 1;    // consider the smallest missing
        
        for(int i = 0; i < n; i++){ 
           if (nums[i] == smallestMissing){ 
              smallestMissing++; 
            } 
        } 
        
        return smallestMissing;
    }

    public static main(String[] args){
        int nums = {7,8,9,11,12};
        Solution solve = new Solution();
        int answer = solve.firstMissingPositive(nums);
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

Explanation

• Initializes an array nums with the values [7, 8, 9, 11, 12] as example.

• Then calls the firstMissingPositive method with array nums and n as argument and stores the answer in the variable answer.

• The length of the array nums is stored in the variable n.

         for (i = 1; i < numsSize; i++) {
    key = nums[i];
    j = i - 1;

    /* Move elements of nums[0..i-1], that are greater than key, 
     to one position ahead of their current position */
    while (j >= 0 && nums[j] > key) {
        nums[j + 1] = nums[j];
        j = j - 1;
    }
    nums[j + 1] = key;
}

• key is the current element being sorted.
• Moves elements that are larger than key to one position ahead, creating space for key.
• Places key in its correct position.

            int smallestMissing = 1;
            for (i = 0; i < numsSize; i++) {
                if (nums[i] == smallestMissing) {
                    smallestMissing++;
                }
            }

• smallestMissing: ` We start with 1, assuming the smallest missing positive number might be 1.

• Check each element in the sorted array.

• If we find the current smallestMissing in the array, we increment it by 1 to check the next number.

• return the smallestMissing.

Follow Up Question: Can you reduce the time complexity of this function.
.
.
.
.
.
.
Hint : Using bucket sort-like idea..
Try it Yourself..

Concept of Insertion Sort Click here.
For more interview problems Click here.

Happy Coding!