Find the smallest missing positive number from an unsorted array
Given an unsorted integer array, find the smallest missing positive integer in it.
For example,
Output: 3
Input: {1, 2, 3, 4}
Output: 5
A simple solution would be to search for all positive numbers in the given array, starting from 1. The time complexity of this solution is O(n2) since the first missing positive number must lie within the range [1, n+1] in an array of size n.
The time complexity can be improved using sorting. The idea is to sort the array and perform a linear scan of the sorted array to find the first missing positive number. The time complexity of this solution is O(n.log(n)). However, the solution is far from optimal. This post provides an overview of some available alternatives to solve this problem in O(n) time.
1. Using Hashing
The idea is to insert all elements (or only positive integers) in the array into a hash set. Like the brute-force approach, do a lookup for positive numbers in the hash set, starting from 1. The smallest positive number missing from the hash set is the result.
The time complexity of this solution is O(n), but requires O(n) extra space for the hash set. Following is the C, C++, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <stdio.h> // Function to find the smallest missing positive number from an unsorted array int findSmallestMissing(int nums[], int n) { // create an auxiliary array of size `n+1` to mark all positive elements int aux[n + 1]; for (int i = 0; i < n + 1; i++) { aux[i] = 0; } // iterate over the array and mark all positive elements in range `[1, n]` for (int i = 0; i < n; i++) { // ignore all non-positive elements and elements greater than `n` if (nums[i] > 0 && nums[i] <= n) { aux[nums[i]] = 1; } } // check for the smallest missing number between 1 and `n` for (int i = 1; i <= n; i++) { if (!aux[i]) { return i; } } // If numbers from 1 to `n` are present in the array, // then the missing number is `n+1` return n + 1; } int main() { int nums[] = { 1, 4, 2, -1, 6, 5 }; int n = sizeof(nums) / sizeof(nums[0]); printf("The smallest positive missing number is %d", findSmallestMissing(nums, n)); return 0; } |
Output:
The smallest missing positive number from the array is 3
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <vector> #include <unordered_set> using namespace std; // Function to find the smallest missing positive number from an unsorted array int findSmallestMissing(vector<int> const &nums) { // use a range constructor to initialize the set from array elements unordered_set<int> distinct(nums.begin(), nums.end()); // return first smallest missing positive number from the set int index = 1; while (true) { if (distinct.find(index) == distinct.end()) { return index; } index++; } } int main() { vector<int> nums = { 1, 4, 2, -1, 6, 5 }; cout << "The smallest missing positive number from the array is " << findSmallestMissing(nums); return 0; } |
Output:
The smallest missing positive number from the array is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.Arrays; import java.util.Set; import java.util.stream.Collectors; class Main { // Function to find the smallest missing positive number from an unsorted array public static int findSmallestMissing(int[] nums) { // use a range constructor to initialize the set from array elements Set<Integer> distinct = Arrays.stream(nums).boxed().collect(Collectors.toSet()); // return first smallest missing positive number from the set int index = 1; while (true) { if (!distinct.contains(index)) { return index; } index++; } } public static void main(String[] args) { int[] nums = { 1, 4, 2, -1, 6, 5 }; System.out.println("The smallest missing positive number from the array is " + findSmallestMissing(nums)); } } |
Output:
The smallest missing positive number from the array is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Function to find the smallest missing positive number from an unsorted array def findSmallestMissing(nums): # initialize the set from array elements distinct = {*nums} # return first smallest missing positive number from the set index = 1 while True: if index not in distinct: return index index += 1 if __name__ == '__main__': nums = [1, 4, 2, -1, 6, 5] print('The smallest missing positive number from the array is', findSmallestMissing(nums)) |
Output:
The smallest missing positive number from the array is 3
2. Using Partitioning logic of Quicksort
The idea is to segregate positive and negative numbers. We can easily do this in linear time and constant space using the Quicksort algorithm’s partitioning technique. The idea is to use 0 as a pivot element and make one pass of the partition process. After the partition step, all positive numbers are put together on one side of the array. The idea is to ignore all non-positive elements and process the subarray containing all positive elements, say nums[0, k-1] for pivot index k.
We initially check if the smallest missing number lies in range 1 to k. To check whether the smallest missing number lies in range 1 to k, use array elements as index and mark array elements as negative, i.e., for each subarray element x, we get the absolute value of the element abs(x) and make the element at index abs(x)-1 negative.
Finally, traverse the subarray once again and find the first index, which has a positive value. If a positive number is located at index i, then the smallest missing number is i+1. If no positive is found, then the smallest missing number must be k+1.
Note that this method modifies the original array. To keep the original array intact, run this approach on an auxiliary array. The algorithm can be implemented in C++, Java, and Python, as shown below:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // Linear time routine for partitioning step of Quicksort int partition(vector<int> &nums) { int pIndex = 0; // each time we find a positive number, `pIndex` is incremented, and // that element would be placed before the pivot for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) // pivot is 0 { swap(nums[i], nums[pIndex]); pIndex++; } } // return index of the first non-positive number return pIndex; } // Function to find the smallest missing positive number from an unsorted array int findSmallestMissing(vector<int> nums) { int k = partition(nums); // Case 1. The missing number is in range 1 to k // do for each array element for (int i = 0; i < k; i++) { // get the value of the current element int val = abs(nums[i]); // make element at index `val-1` negative if it is positive if (val-1 < k && nums[val-1] >= 0) { nums[val-1] = -nums[val-1]; } } // check for missing numbers from 1 to k for (int i = 0; i < k; i++) { if (nums[i] > 0) { return i + 1; } } // Case 2. If numbers from 1 to k are present in the array, // then the missing number is `k + 1` e.g. {1, 2, 3, 4} —> 5 return k + 1; } int main() { vector<int> nums = { 1, 4, 2, -1, 6, 5 }; cout << "The smallest positive missing number is " << findSmallestMissing(nums); return 0; } |
Output:
The smallest positive missing number is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
class Main { // Utility function to swap elements `nums[i]` and `nums[j]` in array `nums` public static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } // Linear time routine for partitioning step of Quicksort public static int partition(int[] nums) { int pIndex = 0; // each time we find a positive number, `pIndex` is incremented, and // that element would be placed before the pivot for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { // pivot is 0 swap(nums, i, pIndex); pIndex++; } } // return index of the first non-positive number return pIndex; } // Function to find the smallest missing positive number from an unsorted array public static int findSmallestMissing(int[] nums) { int k = partition(nums); // Case 1. The missing number is in range 1 to k // do for each array element for (int i = 0; i < k; i++) { // get the value of the current element int val = Math.abs(nums[i]); // make element at index `val-1` negative if it is positive if (val-1 < k && nums[val-1] >= 0) { nums[val-1] = -nums[val-1]; } } // check for missing numbers from 1 to k for (int i = 0; i < k; i++) { if (nums[i] > 0) { return i + 1; } } // Case 2. If numbers from 1 to k are present in the array, // then the missing number is `k + 1` e.g. {1, 2, 3, 4} —> 5 return k + 1; } public static void main(String[] args) { int[] nums = { 1, 4, 2, -1, 6, 5 }; System.out.println("The smallest positive missing number is " + findSmallestMissing(nums)); } } |
Output:
The smallest positive missing number is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
def swap(nums, i, j): temp = nums[i] nums[i] = nums[j] nums[j] = temp # Linear time routine for partitioning step of Quicksort def partition(nums): pIndex = 0 # each time we find a positive number, `pIndex` is incremented, and # that element would be placed before the pivot for i in range(len(nums)): if nums[i] > 0: # pivot is 0: swap(nums, i, pIndex) pIndex += 1 # return index of the first non-positive number return pIndex # Function to find the smallest missing positive number from an unsorted array def findSmallestMissing(nums): k = partition(nums) # Case 1. The missing number is in range 1 to k # do for each array element for i in range(k): # get the value of the current element val = abs(nums[i]) # make element at index `val-1` negative if it is positive if val-1 < k and nums[val-1] >= 0: nums[val-1] = -nums[val-1] # check for missing numbers from 1 to k for i in range(k): if nums[i] > 0: return i + 1 # Case 2. If numbers from 1 to k are present in the array, # then the missing number is `k + 1` e.g. [1, 2, 3, 4] —> 5 return k + 1 if __name__ == '__main__': nums = [1, 4, 2, -1, 6, 5] print('The smallest positive missing number is', findSmallestMissing(nums)) |
Output:
The smallest positive missing number is 3
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)