Solution: First Missing Positive

Let's solve the First Missing Positive problem using the Cyclic sort pattern.

We'll cover the following

Statement

Given an unsorted integer array, nums, return the smallest missing positive integer. Create an algorithm that runs with an O(n)O(n) time complexity and utilizes a constant amount of space.

Note: The smallest missing positive isn’t the first positive number that’s missing in the range of elements in the input, but the first positive number that’s missing if we start from 11.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • −231≤-2^{31} \leq nums[i] ≤231−1\leq 2^{31} - 1

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

  • The brute force approach would be to search for every positive integer in the array, starting from 11 and incrementing the number to be searched until we find the first missing positive number. It will result in an algorithm with the time complexity of O(n2)O(n^2).

  • A solution that everyone thinks about is sorting the array and then searching for the smallest positive number. However, this also gives us a time complexity of O(nlog⁡n)O(n \log n)where n is the number of elements present in our array.

  • The final approach we would discuss is storing all the numbers in a hash table and returning the first positive value we don't encounter. This solution would fulfill the time complexity condition of O(n)O(n) but still requires extra space. That's where cyclic sort comes in.

Optimized approach using cyclic sort

This approach iteratively places each number in its correct position based on the indexes of the array. It involves two key steps: ignoring negative numbers since they don’t affect the search for the missing positive integer and placing the positive numbers at their correct positions. After this, a final array scan where an element does not match its correct position indicates the smallest missing positive number. If all elements are at their correct positions, the smallest missing positive number is one more than the array’s length.

As discussed above, an array of size nn containing numbers ranging from 11 to nn is sorted using the cyclic sort approach in O(n)O(n). So, overall, our problem is solved in O(n)O(n) time and O(1)O(1) space because cyclic sort sorts the elements in place with O(1)O(1) extra space.

Let’s look at the following example to understand this in a better way:

Let’s look at the implementation of the solution discussed above:

import java.util.*;
class FirstMissing {
    public static int firstMissingPositiveInteger(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            int correctSpot = nums[i] - 1;
            if (correctSpot >= 0 && correctSpot < nums.length && nums[i] != nums[correctSpot]) {
                int temp = nums[i];
                nums[i] = nums[correctSpot];
                nums[correctSpot] = temp;
            } else {
                i++;
            }
        }
        for (int j = 0; j < nums.length; j++) {
            if (j + 1 != nums[j]) {
                return j + 1;
            }
        }
        return nums.length + 1;
    }
    // Driver code
    public static void main(String[] args) {
        int[][] A = {
            {1, 2, 3, 4},
            {-1, 3, 5, 7, 1},
            {1, 5, 4, 3, 2},
            {-1, 0, 2, 1, 4},
            {1, 4, 3}
        };
        for (int i = 0; i < A.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tThe first missing positive integar in the list " + Arrays.toString(A[i]) + " is:");
            System.out.println("\t" + firstMissingPositiveInteger(A[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
First Missing Positive

Solution summary

  1. Iterate over all the elements in nums and swap them with their correct position until all elements are in their correct positions.

  2. Iterate over nums again and check if each element is equal to its index plus 1.

  3. If an element is not in the correct position, return the index plus 1, of the element that is out of order, as the smallest missing positive number.

  4. If all elements are in order, return the length of the array plus 1 as the smallest missing positive integer.

Time complexity

The algorithm traverses over the array two times, and in both traversals, it iterates over each element exactly once. Therefore, the time complexity of this algorithm is O(n)O(n), where nn is the length of the nums.

Space complexity

The space complexity of the algorithm is O(1)O(1) as it uses only a constant amount of space.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.