Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1:Brute Force Approach
3.1.
Implementation
3.2.
Complexity Analysis
4.
Approach 2: Sorting 
4.1.
Implementation
4.2.
Complexity Analysis
5.
Approach 3: Hashing/Index Mapping
5.1.
Implementation
5.2.
Complexity Analysis
6.
Approach 4: Changing the Already Existing Array
6.1.
Implementation
6.2.
Complexity Analysis
7.
Frequently Asked Questions
7.1.
What is smallest missing positive integer?
7.2.
What is smallest positive missing number?
7.3.
How do you find the smallest positive integer missing in an array?
7.4.
Is 0 the smallest positive number?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find Smallest Missing Positive Integer

Author Ishita Chawla
0 upvote
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

Find Smallest Missing Positive Integer

Also see, kth largest element in an array and  Euclid GCD Algorithm

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,

smallest positive missing number
smallest missing positive integer

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

Recommended: Try the problem yourself before moving on to the solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1:Brute Force Approach

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

Smallest missing positive integer

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. 

Complexity Analysis

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).

Approach 2: 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

first positive integer index

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. 

Complexity Analysis

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).

Approach 3: 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

Unsorted array

   

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. 

Complexity Analysis

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.

Approach 4: 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

changing existing array
transverse an array
missing integer array
missing positive integer
smallest missing integer

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. 

Complexity Analysis

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).

Check out this problem - Next Smaller Element

You should check out this video to understand the logic behind this problem.

Frequently Asked Questions

What is smallest missing positive integer?

Smallest missing positive integer is a positive integer, that is not present in the given input array. The array can be either sorted or unsorted. The question to find the smallest missing positive integer is a very famous question which is asked many times asked in interviews of big tech companies. 

What is smallest positive missing number?

Smallest missing positive number is a positive number, that is not present in the given input array. The array can be either sorted or unsorted. The question to find the smallest missing positive numberis a very famous question which is asked many times asked in interviews of big tech companies. 

How do you find the smallest positive integer missing in an array?

There can be many ways to find the smallest positive integer missing in an array. One of the methods can be sorting. We just sort the array and iterate from the starting to find the smallest positive integer. Another method can be using a HashMap. The method that will be required will be changing the elements in the array to track which elements are present in the array. 

Is 0 the smallest positive number?

Many students get confused if 0 is the smallest positive integer. But it is not. 0 is not a positive or negative value, it is totally a different value. The number greater than 0 are called positive numbers and the numbers less than 0 are called negative numbers. 

You can also read about - Strong number in c

Conclusion

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

Recommended Problems


Do check out some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.

Previous article
K’th Largest Element in an Array
Next article
Find all triplets with zero-sum
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass