First Missing Positive — Asked in Amazon, Samsung and Snapdeal Interview
Problem Statement :
You are given an array of integers of length N, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can negative numbers as well.
Sample Input:
N = 5Arr = {3, 2, -6, 1, 0}
Sample Output:
4Explanation for Test Case :
The first positive number is 1 and it is present in the array similarly 2 and 3 are also present in the array. 4 is missing from the array. Thus, the minimum positive integer that is missing is 4.
Approach :
Segregation
- Call a function that will segregate the positive integer to the negative integers i.e move all non-positive elements to the right side, and return the index at which non-positive integers start.
- Now we can ignore non-positive elements and consider only the part of the array which contains all positive elements. We traverse the array containing all positive numbers. To mark the presence of an element arr[i], we change the sign of value at index arr[i] to negative i.e mark the presence of element 1 by making the element of array at index 1 to negative, given that the index lies in that segment of positive elements.
- To find the smallest positive missing element, we traverse the positive elements array again and print the first index which has positive value. In case all elements are negative, our index is size — 1. We subtract 1 from the index and that would be the answer.
Time Complexity = O(N)
Space Complexity = O(1)
