Find the element in the order O(n) with a constant extra space.
Example 1:
Input: [ 2, 3, -1, -2] Output: 1
Example 2:
Input: [5, 6, 7, 8, 9] Output: 1
Solution Explanation:
The solution is actually very simple. And we know that an integer starts with 1 to n not zero.
Hence what we do is, first count the number of elements in the array, and fill the given number in it’s index. Suppose we have an array with “n” elements.
We follow below steps to get the result:
Step 1:
Iterate throughout the array Set current_value = arr[i] If current_value < 0 and current_value > array_length Ignore and continue Else Set current_value to the index, whose value is equal to current_value
Step 2:
Once completed step 1, iterate throughout the array to find which smallest index is not having value. You will get your missing element.
Example:
Input:
[2, 3, -1, -2]
Pass 1: Current_value = 2 2 > 0 && 2 > 4 true swap 2 and -1 resulting array: [-1, 3, 2, -2]
Pass 2: Current_value = 3 3> 0 && 3 > 4 true swap 3 and -2 resulting array: [-1, -2, 2, 3]
Pass 3: Current_value = 2 2> 0 && 2 > 4 true as 2 is in already at it’s index, leave it. resulting array: [-1, -2, 2, 3]
Pass 4: Current_value = 3 3> 0 && 3 > 4 true as 3 is in already at it’s index, leave it. resulting array: [-1, -2, 2, 3]
Finally iterating throughout the array:
We find out that the first index i.e arr[1] != 1. Hence the lowest missing element is 1.
Here time complexity is O( n ), because we visit each element once to put it in right place using while [only here number re-arrangement takes place] and finally iterate by using for. Hence O ( n ).
Solution in C language:
#include<stdio.h> int firstMissingPositive(int arr[], int length) { int n = length; int itr = 0; for ( itr = 0; itr < n; itr++) { while (arr[itr] != itr) { // we shall swap for only +ve integers and is less than the length of the array if (arr[itr] <= 0 || arr[itr] >= n) break; //handle duplicate elements if(arr[itr] == arr[ arr [ itr ] ] ) { break; } // swap elements int temp = arr[itr]; arr[itr] = arr[temp]; arr[temp] = temp; } } // start the "itr" value from 0, if you want to consider 0 as smallest +ve integer. for (int itr = 1; itr < n; itr++) { if (arr[itr] != itr) return itr; } return n; } int main() { int arr [100] = {2,1,4,5,6}; int length = 5; int firstMissingPositiveInteger = 0; firstMissingPositiveInteger = firstMissingPositive(arr, length); printf("The smallest missing positive integer is = %d\n", firstMissingPositiveInteger ); }
Output:
The smallest missing positive integer is = 3
Devendra Kumar
Time complexity may goes to ..n^2 in worst case…
Because of two loops…
ajay
In the second loop i.e. for loop, we just iterate through the array to check if the element is present or not. We are not doing any manipulation w.r.t to the number. Hence the time complexity will still remain O ( n ).
Divyanshu Garg
#include
using namespace std;
int main()
{
vectorvect{-1,1,2,3,5};
sort(vect.begin(),vect.end());
stable_partition(vect.begin(),vect.end(),[](int x){return x>0;});
int i=1;
for(int j=0;j<vect.size();j++)
{if(i!=vect[j])
{cout<<i;
break;}
i++;}
return 0;
}