Find the Smallest Missing Positive Number in an Unsorted Array

  • Write a program to find smallest positive missing number in O(n) time and O(1) space.

Given an array of size N which contains positive and negative numbers. We have to find smallest missing positive number.
For Example :
Input Array : -3 4 -2 1 5 2 6 8 7 9
Output : 3

Method 1 : Brute Force
Starting from 1, search every positive number in input array using simple linear search. Return the first positive number which is not present in input array.
Time Complexity : O(n2)
Method 2 : By Sorting Input Array
First of all sort input array using any O(nLogn) sorting algorithm (like quick sort). After sorting just traverse sorted array and return first missing positive numbers.
Time Complexity : O(nLogn + n) = O(nLogn)
Method 3 : Algorithm to find smallest missing positive number in array
Let inputArray be an integer array of size N containing positive and negative numbers.
  • As we have to find smallest positive number, first of all separate negative and positive numbers to reduce our search domain. Here we will use dutch flag algorithm to segregate negative and positive numbers. First all negative numbers and then all positive numbers.
  • After separating negative numbers, now problem reduces to finding smallest missing positive number from an sub array of positive numbers from index K to N-1.
  • Traverse positive element sub array. For an element inputArray[i], to mark it's existence we will togle the value at index inputArray[i] to negative(inputArray[inputArray[i]] *= -1;)
  • Now, traverse the positive sub array again and return the index of first positive element.
Time Complexity : O(n)

C program to find smallest missing positive number

#include <stdio.h>

/*Seperates +ve and -ve numbers in an array. first all -ve and 
then all +ve numbers . THis approach is similar to partition step 
of quick sort */
int seperateNumbers(int *array, int size){
    int temp, left = 0, right = size-1;
    while(right > left){
     /* traverse from left to right till we find a +ve number */
     while(array[left] <= 0)
         left++;
     /* traverse from right to left till we find a -ve number */
     while(array[right] > 0)
         right--;
     
     if(left < right){
            /* Swap array[left] and array[right] */
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
 /* return number of -ve numbers */
 return left;
}

/* Find the smallest missing positive numbers */
int findSmallestPositiveMissing(int *array, int size) {
  int i;

  /* for every element array[i] mark array[array[i] -1] as -ve to
   track existance of element at array[i]. As index starts from 0,
   we are subtracting one from index  */
  for(i = 0; i < size; i++) {
      if(abs(array[i])-1 < size && array[abs(array[i])-1] > 0) {
          array[abs(array[i])-1] =  -1 * array[abs(array[i])-1];
      }
  }
 
  /* After complete traversal of array, if any element array[i] 
  is _ve number than i+1 is not present in array */
  for(i = 0; i < size; i++) {
    if (array[i] > 0) {
     return i+1;
    }
  }
  /* If in an array of length L, all +ve numbers from 1 to L 
  is present then it means first missing number is L+1 */
  return size+1;
}

int getMissingPosNumber(int *array, int size) {
    /*  Seperate _ve and -ve numbers */
    int count = seperateNumbers(array, size);
    /* Find first missing positive number */
    printf("%d\n", findSmallestPositiveMissing(array+count, size-count));
}

int main(){
    int i, array[10] = {-3, 4, -2, 1, 5, 2, 6, 8, 7, 9}; 
    
    getMissingPosNumber(array, 10);

    return 0;
}
Output
3
Posted by
Labels: ,