First Missing Integer | Arrays | O(N) Time | O(1) space | C++

 

Problem Description:

Given an unsorted integer array, find the first missing positive integer.

Example:

Given [1,2,0] return 3,

[3,4,-1,1] return 2,

[-8, -7, -6] returns 1

Your algorithm should run in O(n) time and use constant space.

Approach:

 We use array elements as the index. To mark the presence of an element x, we change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So we segregate positive from negative numbers as the first step and then apply the approach.

Following is the two-step algorithm.
1) Segregate positive numbers from others i.e., move all non-positive numbers to the left side. In the following code, segregate() function does this part.
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 and to mark the presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has a positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.

Problem Solution in C++ Programming Language:

code:

class Solution {

    public:

        int firstMissingPositive(vector<int> &A) {

            int n = A.size();

            for (int i = 0; i < n; i++) {

                if (A[i] > 0 && A[i] <= n) {

                    int pos = A[i] - 1;

                    if (A[pos] != A[i]) {

                        swap(A[pos], A[i]);

                        i--;

                    }

                }

            }

            for (int i = 0; i < n; i++) {

                if (A[i] != i + 1) return (i + 1);

            }

            return n + 1;

        }

};

Please share your reviews.

thanks for reading.👍😊

If you like the solution please share with your friends.

and for more dynamic programming question for interview preparation.