First Missing Positive Problem (C++, Java, Python)

Finding missing numbers can easily be found by iterating over the array or through a binary search. But there is also a question of finding a duplicate which is the same as the missing number in a sorted array but if we make the array unsorted it becomes a difficult version of it. So in this article, we will discuss the First Missing Positive problem and try to solve it using different approaches.

What is the First Missing Positive problem?

In the First Mission Positive problem, you are given an array, and you must find the first positive integer missing from that array.

This is important to note that if you are not given that the array is sorted always consider it unsorted and as it was not specified in the question the values of the array are only positive so we have to consider that it may contain negative values also. 

For example, you are given array arr= [2, 1, -1, -3] in this case the ans is 3 as 1 and 2 are already present so the first missing positive number is 3. We are not returning 0 as 0 is neither positive nor negative.

Naive Approach

The basic solution is to check for each positive number in the given array and if it is not present then that number will be the first missing positive number. Let’s understand by an example:

• Given array:

• First check for 1 in the array as 1 is present, and then we move to the next number:

• Check for number 2 as 2 is also present, check for next:

• Check for number 3 as 3 is not present in the array so 3 will be the answer.

As we are checking for each number in the array, the maximum we need to check is the size of the array let’s say of array is n so the time complexity is O(n^2).  Space Complexity will be O(1) as we are not using any extra space.

Sorting to Find the First Missing Positive

As in the above approach, we see that the time complexity is around O(n^2) which is huge and we know we can easily find the first missing number in the sorted array just by iterating over that array.

To find the first missing positive in an array, we will first sort the array by sorting function and then make an int variable x=1 whose initial value will be 1 and keep on updating if it encounters the same value.

For example, let’s take an array:

• After sorting array would be like this:

• Let’s take a variable x=1, now iterate over the array, and increment the array value if it is the same as the variable and if the variable value is less than the current value of the array return the variable value.

• In this case, the value it returns will be 3.

As we are sorting the array and iterating the array for once the time complexity would become (n+ log (n)) which is approx O(nlog(n)). Here n is the size of the array. Space Complexity will be O(1) as we are not using any extra space.

Optimized Sorting with Swap Approach

As in the sorting approach time complexity is around O(log (n)) which is still too much. We can reduce this to O(n) by just observing the pattern as we know we have to find the first positive missing number.

We just keep on putting the positive value to its correct place if possible (as sometimes the positive value is larger than the size of the array in that case we cannot put this to its correct index) whenever we find they are not at the right position. 

Let’s take an example:

1. First, iterate over the array and check if the value at the current index is more than 0 and less than the index+1 or not. 
2. If not then move to the next index.
3. Else check arr[arr[i]-1] <= arr[i] i.e. if the value present at the index, which is the same as the value of the current index is less than the current index value or not. If it is then change the value of arr[arr[i]-1]= -1. We are doing this as some values might be the same for example in arr[1, 2, 2, 4] when we are at index 3 we find out the value is 2, and at the 2nd index is also value 2 so we will change the 2nd index value to -1 and then swap 2nd and 3rd index.

C++ Code

Here is the C++ program to solve the First Missing Positive problem:

#include <bits/stdc++.h>
using namespace std;

int main(){

    vector<int> arr= {1,2,4,2,-1,0,5};
    int i=0;
    // n is the size of the array
    int n= arr.size();

    // iterating over the array
    while(i<n){
        //checking if value at that index is less than that index or not 
        if((i+1)>arr[i] && arr[i]>0){
            // if value present at the index which is equal to the value of the current index is less than or equal to the value of the current index update the previous value to -1.
            if(arr[arr[i]-1]<=arr[i]) arr[arr[i]-1]=-1; 
            // now swap the value at the current index and the value at the index where the index is the same as the value of current index
            swap(arr[arr[i]-1], arr[i]);
        }
        else i++;
    }

    //checking for the first missing +ve number  
    for(i=0; i<n;i++){
        if(arr[i]<=0 || arr[i]!=i+1) {
            cout<<i+1<<endl;
            goto he;
        }
    }

    cout<<n+1<<endl;
    he:;
    
    return 0;
}

Java Code

Here is the Java program to solve it:

import java.util.*;

class Main {
    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 4, 2, -1, 0, 5));
        int i = 0;
        int n = arr.size();

        while (i < n) {
            if ((i + 1) > arr.get(i) && arr.get(i) > 0) {
                if (arr.get(arr.get(i) - 1) <= arr.get(i)) {
                    arr.set(arr.get(i) - 1, -1);
                }
                int temp1 = arr.get(i);
                int temp2 = arr.get(arr.get(i)-1);
                arr.set(temp1-1, temp1);
                arr.set(i, temp2);
            } else {
                i++;
            }
        }

        boolean flag=false;
        for (i = 0; i < n; i++) {
            if (arr.get(i) <= 0 || arr.get(i) != i + 1) {
                System.out.println(i + 1);
                flag=true;
                break;
            }
        }

        if(flag==false) System.out.println(n + 1);
    }
}

Python Code

You can implement it in Python with the following code:

def main():
    arr = [1, 2, 4, 2, -1, 0, 5]
    i = 0
    n = len(arr)

    while i < n:
        if 0 < arr[i] < i + 1:
            if arr[arr[i] - 1] <= arr[i]:
                arr[arr[i] - 1] = -1
            arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i] - 1]
        else:
            i += 1

    for i in range(n):
        if arr[i] <= 0 or arr[i] != i + 1:
            print(i + 1)
            break
    else:
        print(n + 1)


if __name__ == "__main__":
    main()

Output:

3

As we are just moving once in the loop the time complexity is O(n). Space Complexity will be  O(1) as we are not using any extra space.

Finally, here is a small comparison of the three methods:

Conclusion 

We have seen various approaches to solving the First Missing Positive leetcode problem which helps to understand how can we reduce the time complexity from O(n^2) to O(n). This problem might be solved with other approaches too by making a temporary array or with the use of a hash map all these can either increase the time or space complexity.