### Program to Find first missing positive number in unsorted array in java

In this core java programming tutorial we will write following program in java >

Program 1 to Find first missing positive number in an unsorted array in java.
You are given an unsorted array of positive and negative numbers, find first missing positive number from that unsorted array in java

Logic will be>
• sort the array - we will use Merge sort to offer best complexity.
For sorting the array we will use merge sort which offers one of the best complexity i.e.  O(N*logN)
• find the index of first positive number.
• Than iterate from firstPositiveNumberIndex till first positive number is not missing.
complexity i.e.  O(N)

Overall complexity of program will be O(N*logN) + O(N) in java.

This program could also be a simple Level2 program but I have kept this as Level3 program because I am using merge sort for sorting.
Using sorting algorithm like Bubble Sort, Selection Sort and Insertion Sort will offer o(n2) complexity.

Example  in java -
{3,0,1,8,-1,7,-11,10}   -   2 is missing

{1, -2, 3, 5, 4, 2 , -4}   -   No number is missing

{1, -2, 3, -9, 0, 8, -90,2}   -   4 is missing

{1, 0, 2 }   -   No number is missing

{1, 0, 2, 4}   -   3 is missing

Program/ Example 1 to Find first missing positive number in an unsorted array in java.

 /** Copyright (c), AnkitMittal JavaMadeSoEasy.com */ public class  FindFirstMissingPositiveNumber {       static int ar[]={0,1,2,-2,5,7,3,4}; //6 is missing       public static void main(String[] args) {       //first sort array - we will use Merge sort       int[] ar2 = new int[ar.length];           mergeSort(ar2, 0, ar.length - 1);                 //display array       display();             //Now let's find first missing positive number       findFirstMissingPositiveNumber();          }       static void findFirstMissingPositiveNumber(){       int firstPositiveNumberIndex = -1;       for(int i=0;i -1){                                   //iterate from firstPositiveNumberIndex till first positive number is not missing                  if( (i-firstPositiveNumberIndex+1) != ar[i]){                               System.out.println( (i-firstPositiveNumberIndex+1) + " is missing");                               return;                        }           }           //Find index of first positive number           else if(ar[i] >=1){                                if(ar[i]!=1){                        System.out.println("1 is missing");                        return;                  }                  firstPositiveNumberIndex = i;           }       }       System.out.println("No number is missing");    }       /*    * method performs merge sort.    */    static void mergeSort(int[] workSpace, int lowerBound, int upperBound) {           if (lowerBound == upperBound){                  return;    //no need to sort further.           }else {    // finding mid point                  int midPoint = (lowerBound + upperBound) / 2;                  mergeSort(workSpace, lowerBound, midPoint); // sorting low half                  mergeSort(workSpace, midPoint + 1, upperBound); // sort upper half                  merging(workSpace, lowerBound, midPoint + 1, upperBound)   -   merging them           }    }          static void merging(int[] ar2, int low, int high, int upperBound) {               int midPoint = high - 1;           int lowerBound = low;           int n = upperBound - lowerBound + 1;           int i = 0;                     while (low <= midPoint && high <= upperBound)                  if (ar[low] < ar[high])                        ar2[i++] = ar[low++];                  else                        ar2[i++] = ar[high++];                     while (low <= midPoint)                  ar2[i++] = ar[low++];                     while (high <= upperBound)                  ar2[i++] = ar[high++];                     for (i = 0; i < n; i++)                  ar[lowerBound + i] = ar2[i];              }       static void display(){           for(int i=0;i

Note : 1 is the first positive number, not zero.

Program/ Example 2 to Find first missing positive number in an unsorted array which may consist of duplicate numbers in java.

Logic and complexity of program will be same as above program.

Example  -

{0,1,2,-2,5,7,3,1,4}   -   6 is missing

{3,0,1,8,-1,7,1,-11,10}   -   2 is missing

{1,2,3,1}   -   No number is missing

{ 1, -2, -9, 0, 8, 7, 5, 6, 0, 1, -1, -90, 2, 2, 2, 4 }   -   3 is missing

 /** Copyright (c), AnkitMittal JavaMadeSoEasy.com */ public class  FindFirstMissingPositiveNumberDuplicateNumbers {       static int ar[] = {1, -2, -9, 0, 8, 7, 5, 6, 0, 1, -1, -90, 2, 2, 2, 4 }  -  3 is missing       public static void main(String[] args) {       //first sort array - we will use Merge sort   int[] ar2 = new int[ar.length];           mergeSort(ar2, 0, ar.length - 1);             //display array       display();             //Now let's find first missing positive number       findFirstMissingPositiveNumber();          }       static void findFirstMissingPositiveNumber(){       int firstPositiveNumberIndex = -1;       for(int i=0;i -1){                                   //Just add small logic here to detect number is same as previous or not                  if(ar[i]== ar[i-1]){                        //Increase firstPositiveNumberIndex to counter the duplicate numbers in array                        firstPositiveNumberIndex++;                        continue;                  }                                         //iterate from firstPositiveNumberIndex till first positive number is not missing                  if( (i-firstPositiveNumberIndex+1) != ar[i]){                               System.out.println( (i-firstPositiveNumberIndex+1) + " is missing");                               return;                        }           }           //Find index of first positive number           else if(ar[i] >=1){                                if(ar[i]!=1){                        System.out.println("1 is missing");                        return;                  }                  firstPositiveNumberIndex = i;           }       }       System.out.println("No number is missing");    }       /*    * method performs merge sort.    */    static void mergeSort(int[] workSpace, int lowerBound, int upperBound) {           if (lowerBound == upperBound){                  return;    //no need to sort further.           }else {    // finding mid point                  int midPoint = (lowerBound + upperBound) / 2;                  mergeSort(workSpace, lowerBound, midPoint); // sorting low half                  mergeSort(workSpace, midPoint + 1, upperBound); // sort upper half                  merging(workSpace, lowerBound, midPoint + 1, upperBound)   -   merging them           }    }          static void merging(int[] ar2, int low, int high, int upperBound) {               int midPoint = high - 1;           int lowerBound = low;           int n = upperBound - lowerBound + 1;           int i = 0;                     while (low <= midPoint && high <= upperBound)                  if (ar[low] < ar[high])                        ar2[i++] = ar[low++];                  else                        ar2[i++] = ar[high++];                     while (low <= midPoint)                  ar2[i++] = ar[low++];                     while (high <= upperBound)                  ar2[i++] = ar[high++];                     for (i = 0; i < n; i++)                  ar[lowerBound + i] = ar2[i];              }       static void display(){           for(int i=0;i

Having any doubt? or you you liked the tutorial! Please comment in below section.