Browse Categories
Choose your Categories to read

Find Smallest Missing Positive Integer

Ishita Chawla
Oct 28, 2021

Introduction

There are many algorithms to solve a problem. But we need to choose the best one out of the many that exist to provide an optimal solution to our problem.

Performance analysis is vital for any problem that you may solve in Data Structures and Algorithms as it enhances a person's logical ability.

In this blog, we will be discussing a prevalent problem of finding the smallest missing positive integer from an unsorted array. We will apply various techniques and then conclude which one is the best in terms of time and space complexity. 

Problem Statement:

The task is to find the smallest missing positive integer from an unsorted array ARR of length N, containing positive and negative integers.

Note: You are allowed to modify the array.

For example,

We will try to solve this problem using four different approaches to get a better understanding of concepts.

Brute Force:

Since the total number of elements in the array is N thus, the smallest positive integer missing from the array will lie in the [1N+1] range. 

The brute force approach uses a nested loop to traverse the array and search for all the numbers one by one, from to N+1, to find the missing integer 

Example:

Let us consider an unsorted array ARR of length 7

Since N = 7, we will start from i = and move on till we reach i = 7, i.e., the (N)th number. If we find all the numbers less than or equal to 7, the answer will be 8

For every i, we traverse through the array using two loops and find whether it is present in the array or not. In this case, we find that the missing number is 4. 

Implementation

// C++ Program to find the smallest missing positive number from an unsorted array.

// Using Brute Force Approach.
#include <bits/stdc++.h>
using namespace std;

// Function to return the smallest positive missing positive integer.
int findSmallest(vector<int> &arr, int n)
{
    bool flag = false;
    int x = 0;

    // Searching for all elements from 1 to 'N' using a nested 'For' loop.
    for (int i = 1; i <= n + 1; i++)
    {
        // Initialising flag to false every time the second loop runs.
        flag = false;
        for (int j = 0; j < n; j++)
        {
            // In case the element is found, flag becomes true.
            // x is initialised as the number which is found in the array.
            if (arr[j] == i)
            {
                flag = true;
                x = i;
                break;
            }
        }

        // In case the element is not found.
        if (flag == false)
            break;
    }

    // x + 1 gives the smallest number that is missing in the array.
    return x + 1;
}
int main()
{
    vector<int> arr;
    int n, i, a;

    // Taking user input.
    cout << "Enter the number of elements\n";
    cin >> n;
    cout << "Enter the elements\n";
    for (i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
    // Calling the function.
    cout << "The smallest missing positive integer is " << findSmallest(arr, n);
    return 0;
}

Input:

Enter the number of elements:

7

Enter the elements:

-1

5

0

1

7

3

2

Output:

The smallest missing positive integer is 4. 

Time Complexity

Since we traverse the entire array for every i in the range [1, N+1], the time complexity of this approach is given by O(N*N) or simply O(N2).

Space Complexity

Since no extra space is used, the space complexity is constant, i.e., O(1).

Sorting 

Another approach for solving the problem in a better time complexity is to use sorting. 

We first sort the array. We can either apply an inbuilt function or apply a sorting algorithm like Merge Sort. The only reason to use Merge Sort is better time complexity, even in the worst case. Other sorting algorithms like Quick SortInsertion Sort, etc., have a worst-case time complexity of O(N2).

The next step is to search for the index where the first positive integer lies. After this, we just have to check the difference between 2 consecutive numbers, i.e., if the difference is greater than 1, it is clear that at least one number is missing between them. Therefore the answer is given by 1 added to the smaller number. This takes linear time.

As a result, this approach provides a better time complexity than the brute force approach.

Example:

Let us consider the same unsorted array ARR of length 7

Now, we will linearly traverse the array from index 2, calculating the difference between the consecutive integers.

We see that ARR[5] - ARR[4] = 2  

Since the difference is greater than 1, a number is missing. This missing number is given by 3 + 1 = 4.

Thus, 4 is missing in the given array.

Implementation

// C++ Program to find the smallest missing positive number from an unsorted array.
// Using Sorting Technique.

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

int findSmallest(vector<int> &arr, int n)
{
    int x = 0, y;
    bool flag = true;

    // Sorting the array initially.
    sort(arr.begin(), arr.end());

    // Searching for the index where the first positive integer is present.
    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= 0)
        {
            // Storing the index in variable x.
            x = i;
            break;
        }
    }

    // If the first positive integer is greater than 1 and 0 is also missing, in that case the missing integer would be 1.
    if (arr[x] > 1)
        return 1;

    // Iterating through the array from the index x which contains the first positive number.
    for (int i = x; i < n - 1; i++)
    {
        // If the difference between 2 consecutive numbers is greater than 1,
        // It means one or more than one number is missing.
        if (arr[i + 1] - arr[i] > 1)
        {
            flag = false;
            y = arr[i];
            break;
        }
    }

    // If the value of the flag is true, the missing number will be given by ARR[N+1].
    // Else it is given by y+1.
    return (flag ? arr[n - 1] + 1 : y + 1);
}
int main()
{
    vector<int> arr;
    int n, i, a;

    // Taking user input.
    cout << "Enter the number of elements\n";
    cin >> n;
    cout << "Enter the elements\n";
    for (i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }

    // Calling the function.
    cout << "The smallest missing positive integer is " << findSmallest(arr, n);
    return 0;
}

Input:

Enter the number of elements:

7

Enter the elements:

-1

5

0

1

7

3

2

Output:

The smallest missing positive integer is 4. 

Time Complexity

First, we sort the array, which takes the time of O(N*(log N)). Then we traverse the entire array using a loop to find the index of the first positive integer, which takes O(N) time in the worst case. At the end, we used another for loop for finding the missing positive integer, which will also take O(N) time in the worst case. As a result, the overall time complexity is given by O(N + N + N*(log N)) which is equal to O(N*(log N)).

Space Complexity

Since no extra space is used, the space complexity is constant, i.e., O(1).

Hashing/Index Mapping

To improve the time complexity, we now take a hashtable/map to solve the problem. 

We iterate over the array linearly and mark only the positive numbers as true in the hashmap.

Then, we traverse from 1 to N + 1 and check whether the values on these keys are true or not. If the value is false, it means that the number is not present in the array, and whenever we encounter a false, we break the loop as we have found the smallest missing positive number. 

This will become more clear with the help of the following example.

Example:

Let us consider the same unsorted array ARR of length 7

   

Starting from 1, we see that the number 4 is not present on our map. Thus, 4 is the smallest missing number in the given array.

Implementation:

// C++ Program to find the smallest missing positive number from an unsorted array.

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

// Function to return the smallest missing positive integer.
int findSmallest(vector<int> &arr, int n)
{
    // Declaring a hashmap.
    unordered_map<int, bool> hashMap;
    for (int i = 0; i < n; i++)
    {
        // Storing the values of positive integers in the map.
        if (arr[i] > 0)
            hashMap[arr[i]] = true;
    }

    // Traversing the elements from 1 to n.
    for (int i = 1; i <= n; i++)
    {
        // If the element is not found in the map, return it.
        if (hashMap[i] == false)
        {
            return i;
        }
    }
    // If all elements from 1-n are present in the map, n+1 is the required answer.
    return n + 1;
}

int main()
{
    vector<int> arr;
    int n, i, a;

    // Taking user input.
    cout << "Enter the number of elements\n";
    cin >> n;
    cout << "Enter the elements\n";
    for (i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }

    // Calling the function.
    cout << "The smallest missing positive integer is " << findSmallest(arr, n);
    return 0;
}

Input:

Enter the number of elements:

7

Enter the elements:

-1

5

0

1

7

3

2

Output:

The smallest missing positive integer is 4. 

Time Complexity

We first iterate over the array and store the numbers in a hashmap, and insertion of an element in a hashmap takes constant time. In this case, we are inserting elements into the hashmap. Thus, this operation takes N * O(1) = O(N) time.

Now, we traverse the hashmap to find the missing element. In the worst case, we will have to traverse over the entire map and it will take O(N) time. 

Thus, the overall time complexity is given by O(N + N) = O(N).

Space Complexity

Since extra space is used to create a hash table/map, the space complexity is given by O(N), where ‘N’ is the number of the positive integers in the array.

Changing the already existing array

This approach is slightly different from the above ones as it does not use extra space and changes the already existing array to find the smallest missing positive integer. Let us understand it through the following steps:

  1. The smallest positive integer that can be missing in the array is 1. So, we search for 1 in the array. If it is not present, the answer is 1. 

2. If 1 is present, we traverse the array again. If we find any number less than 1 or greater than N when traversing the array, we shall set it to 1. This will have no effect on our answer because it will always lie between and N + 1 . The resulting array will now include items ranging from 1 to N.
3. Now we will again traverse the array and for every i, we will perform the following operation:

ARR[ ( ARR[i] - 1 ) % N ] + = N

What we've done is increase the value of the element at that index by N for each element.

4. We will find the first index, iwhich still has a value between 1 and N+1. The answer will be (i+1).

Let us take an example to be more clear.

Example:

Let us consider the same unsorted array ARR, of length 7

Now we iterate through the array and find the smallest index with the value between 

1 and 7. Index 3 contains 1; thus 3 +4 is the smallest missing number in the given array.

Implementation:

// C++ Program to find the smallest missing positive number from an unsorted array.
// Using mapping in the same array.
#include <bits/stdc++.h>
using namespace std;

// Function to return the smallest number.
int findSmallest(vector<int> &arr, int n)
{
    bool flag = false;

    // Searching for 1 in the array.
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 1)
        {
            flag = true;
            break;
        }
    }

    // If 1 is not found, it is the smallest missing number.
    if (flag == false)
        return 1;

    // If a number is less than 0, or greater than 1, it is converted into 1.
    for (int i = 0; i < n; i++)
    {
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;
    }

    // The indexes are updated according to the values.
    for (int i = 0; i < n; i++)
    {
        arr[(arr[i] - 1) % n] += n;
    }

    // Searching for the index which has a value less than n.
    for (int i = 0; i < n; i++)
    {
        if (arr[i] <= n)
            return i + 1;
    }

    // In case values of all indexes are greater than n.
    return n + 1;
}
int main()
{
    vector<int> arr;
    int n, i, a;

    // Taking user input.
    cout << "Enter the number of elements\n";
    cin >> n;
    cout << "Enter the elements\n";
    for (i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }

    // Calling the function.
    cout << "The smallest missing positive integer is " << findSmallest(arr, n);
    return 0;
}

Input:

Enter the number of elements:

7

Enter the elements:

-1

5

0

1

7

3

2

Output:

The smallest missing positive integer is 4. 

Time Complexity

Since, in this approach we traverse the array linearly every time, to search for the missing number, the time complexity is given by O(N).

Space Complexity

Since no extra space is used, the space complexity is constant, i.e., O(1).

Key Takeaways

So, this blog discussed the different approaches to find the smallest missing positive integer in an unsorted array along with the time and space complexity of each technique.

To learn more, head over right now to CodeStudio to practice problems on arrays and crack your interviews like a Ninja!

In case of any comments or suggestions, feel free to post them in the comments section.

By Ishita Chawla

Was this article helpful ?
0 upvotes