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:

4

Explanation 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

  1. 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.
  2. 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.
  3. 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)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store