First missing positive

Table of Contents

Problem Statement

“First missing positive” problem states that you are given an array a[ ] (sorted or unsorted) of size n. Find the first positive number that is missing in this array.

Example

First Missing Positive

a[ ] = {1, 3, -1, 8}

Explanation: If we sort the array we get {-1, 1, 3, 8}. We are not dealing with negative integers so it does not matter if we have -1/0 or not. But after that, we are concerned if the array has numbers from 1 or not. So, 1 is present and then the next number is 3. But 2 is missing. So that becomes our first positive integer that is not present in the array.

a[ ] = {9, -1, 8, 7}

Explanation: Once again we try to sort the array and then check until where we have the positive integers starting from 1. So after sorting we have {-1, 7,8,9}. Thus we know the first positive integer is 1 that is not present in the array.

Approach

Using Sorting

Algorithm to find first missing positive

1. Initialize a non-empty array a[ ] of size n.
2. Initialize an integer variable min as 1 to store the smallest positive missing element.
3. Sort the given array a[ ] of size n.
4. Traverse through the array a[ ] and check if the element at the current index in array a[ ] is equal to the variable min, increment the variable min by 1.
5. Return the variable min.

So, explained above during the input/output section we were first sorting the input and were then checking for the first positive integer that is not present in the array. But since we have used sorting, this method is not efficient enough.

Code

C++ Program to find first missing positive

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

int missPositive(int a[], int n){ 
    int min=1;
    sort(a, a+n);
    for(int i=0; i<n; i++){
        if(a[i]==min){
            min++;
        }
    }
    return min;
}  
int main(){ 
    int a[] = {9, -1, 1, 8, 7}; 
    int n = sizeof(a)/sizeof(a[0]);
    cout<<missPositive(a, n); 
    return 0; 
}

Java Program to find first missing positive

import java.util.Arrays;
class missing{
    static int missPositive(int a[], int n){ 
        int min=1;
        Arrays.sort(a);
        for(int i=0; i<n; i++){
            if(a[i]==min){
                min++;
            }
        }
        return min;
    }
  public static void main (String[] args){
        int a[] = {9, -1, 1, 8, 7};
        int n = a.length;
        System.out.println(missPositive(a, n));
  }
}

Complexity Analysis

Time Complexity

O(N log N) where n is the number of elements in the given array a[ ].

Space Complexity

O(N) because we used space for storing n elements.

Efficient Method

Algorithm to find first missing positive efficiently

1. Initialize a non-empty array a[ ] of size n.
2. Initialize two variables of integer type val and nextval to store the current element and the next element of the array respectively.
3. Traverse through the array a[ ] and check if the element at current index in array a[ ] is greater than 0 or the element at current index in array a[ ] is greater than the array size store it in val. Traverse the array until we reach an element that is already marked or could not be marked.
4. Again Traverse the array and find the first array index which is not marked and is the smallest missing number. Return index + 1.
5. Else if all the index are marked return n +1.

So in the naive approach, we sorted the array. And then searched for the answer. Here we are not going to sort the array instead of that we will be marking our array. By marking I meant, we will be placing the elements at the index equal to the value of the element. That way we will be able to check which number is the first missing positive.

Code

C++ Program to find first missing positive

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

int missPositive(int a[], int n){ 
    int num, nextnum; 
    for(int i=0; i<n; i++){ 
        if ((a[i]<=0) || (a[i]>n))
            continue; 
  
        num = a[i]; 
  
        while(a[num - 1] != num) { 
            nextnum = a[num - 1]; 
            a[num - 1] = num; 
            num = nextnum; 
            if ((num<=0) || (num>n)) 
                break; 
        } 
    } 
    for(int i=0; i<n; i++) { 
        if (a[i] != i+1) { 
            return i+1; 
        } 
    } 
    return n + 1; 
}  
int main(){ 
    int a[] = {9, -1, 1, 8, 7}; 
    int n = sizeof(a)/sizeof(a[0]);
    cout<<missPositive(a, n); 
    return 0; 
}

Java Program to find first missing positive

class missing{
    static int missPositive(int a[], int n){ 
        int num, nextnum; 
      
        for(int i=0; i<n; i++){ 
            if (a[i] <= 0 || a[i] > n) 
                continue; 
      
            num = a[i]; 
      
            while(a[num - 1] != num) { 
                nextnum = a[num - 1]; 
                a[num - 1] = num; 
                num = nextnum; 
                if (num <= 0 || num > n) 
                    break; 
            } 
        } 
      
        for(int i=0; i<n; i++) { 
            if (a[i] != i+1) { 
                return i+1; 
            } 
        } 
        return n + 1; 
    }  
  public static void main (String[] args){
    int a[] = {9, -1, 1, 8, 7}; 
    int n = a.length;
    System.out.println(missPositive(a, n));
  }
}