#### 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 **0**s & **1**s.

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; }