Do you think IIT Guwahati certified course can help you in your career?
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.
The task is to find the smallest missing positive integer from an unsortedarrayARR 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.
Recommended: Try theproblemyourself before moving on to the solution.
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 [1, N+1] range.
Thebrute force approach uses a nested loop to traverse the array and search for all the numbers one by one, from1 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 =1 and move on till we reach i =7, i.e., the (N)thnumber. 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;
}
You can also try this code with Online C++ Compiler
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 Sort, Insertion 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 2 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;
}
You can also try this code with Online C++ Compiler
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 ahashtable/mapto 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;
}
You can also try this code with Online C++ Compiler
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 N 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:
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 1 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, i, which 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 +1 = 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;
}
You can also try this code with Online C++ Compiler
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.
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.
569+ registered 
