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