The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Find the smallest positive element missing in the given array of size 'n' consisting of both positive & negative integers.
Consider the array { -8, 3, 2, -4, 6, 1, 5 } .
Smallest positive element missing in the array is 4.

Solution :-
We might think of an approach in which we start searching the array for positive integers starting from 1 and look for the first missing element. This is a very inefficient approach.
We can also use hash table where positive integers are the keys and values denote their presence in the array. If a value 'x' is present, hash_map[x] is set to 1, else 0. Then we traverse the hash_map to look for first key with value set to 0.
This is efficient in terms of time complexity but not so efficient if we consider the space complexity.
We will go for an approach best in terms of both time and space complexity.
First let's divide the array in two halves. First half consisting of negative elements only & 2nd half consisting of positive elements. This can be done with the same logic discussed in sorting an array of 0s & 1s.
Then we consider the positive half of the array and find the smallest missing element extending the logic discussed in find duplicate elements in the array.
If we see element 'x', we make the element at pos_half(x) negative.
Then we traverse the positive half again to look for 1st negative value. The index of that value is the smallest positive element missing in the array. See the implementation below.

#include<iostream>
#include<cmath>
using namespace std;

// swap elements of two indexes in the array
void swap (int arr[], int pos1, int pos2) {
   int temp = arr[pos1];
   arr[pos1] = arr[pos2];
   arr[pos2] = temp;
}

// classfies the postive and non-positive elements
// into two sections within the array
// sample i/p :: 7,-8,57,6,0,1,19,-4,-7,2
// sample o/p :: -7 -4 -8 0 6 1 19 57 7 2
// returns the index of the first positive element
int classifyPosNeg(int arr[],int size) {
   int j = size-1;
   int i = 0;
   // start traversing the array from end
   while (j >= i ) {
      if (arr[j] <= 0) {
         // move the non-positive no.s to the portion of 
         // array where all non-pos no. are present and 
         // increase their boundary towards right
         swap(arr,i,j);
         i++;
      }
      else {
         // don't do anything if pos no. is found
         j--;
      }
   }
   return i;
}

// finds the smallest positive element which is missing in the
// given array
int findSmallestMissingPosElement(int arr[],int size) {
   // classify the elements into two portions
   // get the index of first pos element
   int pos_start = classifyPosNeg(arr,size);
   arr = arr + pos_start; // shift the array
   size = size - pos_start; // update the new array size
   int i;
   for (i=0;i<size;i++) {
      int k = abs(arr[i]);
      // 'k-1' since array index starts at 0
      if (arr[k-1] > 0 && (k-1) < size) {
         // mark the element 'k' as present by
         // negating the value at index k-1
         arr[k-1] = -arr[k-1];
      }
   }
   // look for the first positive value in the shifted array
   for (i=0;i<size;i++) {
      if (arr[i] > 0) {
         // implies i+1 was not seen in the array
         // so 'i+1' is missing
         return i+1;
      }
   }
   return size+1;
}

// main
int main() {
   int arr[] = {7,-8,57,6,0,1,19,-4,-7,2};
   int size = sizeof(arr)/sizeof(arr[0]);
   int missing_element = findSmallestMissingPosElement(arr,size);
   cout<<"\nSmallest Positive missing element is "<<missing_element;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)