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<ar.length;i++){
         
          //Enter if loop only when we have already found index of first positive number
          if(firstPositiveNumberIndex > -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<ar.length;i++){
          System.out.print(ar[i]+" ");
      }
          System.out.println();
   }
}
/*OUTPUT
-2 0 1 2 3 4 5 7
6 is missing
*/

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<ar.length;i++){
         
          //Enter if loop only when we have already found index of first positive number
          if(firstPositiveNumberIndex > -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<ar.length;i++){
          System.out.print(ar[i]+" ");
      }
          System.out.println();
   }
}
/*OUTPUT
-2 0 1 2 3 4 5 7
6 is missing
*/



Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.




RELATED LINKS>


>Pattern/Pyramid generating programs




No comments:

Post a Comment