Problem

Given an unsorted integer array, find the first missing positive integer.

Follow up

You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array.

Examples

Example 1:

Input:
nums = [1,2,0]
Output:
 3

Example 2:

Input:
nums = [3,4,-1,1]
Output:
 2

Example 3:

Input:
nums = [7,8,9,11,12]
Output:
 1

Solution

Method 1 - Naive Approach

A naive method to solve this problem is to search all positive integers, starting from 1 in the given array. We may have to search at most n+1 numbers in the given array. So this solution takes O(n^2) in worst case.

Method 2 - Sorting

We can use sorting to solve it in lesser time complexity. We can sort the array in O(nLogn) time. Once the array is sorted, then all we need to do is a linear scan of the array. So this approach takes O(nLogn + n) time which is O(nLogn).

Method 3 - Hashing

We can also use hashing. We can build a hash table of all positive elements in the given array. Once the hash table is built. We can look in the hash table for all positive integers, starting from 1. As soon as we find a number which is not there in hash table, we return it. This approach may take O(n) time on average, but it requires O(n) extra space.

Method 4 - Use Absolute with Number as Index

We use array elements as index. We have - Find duplicate number in array containing n+1 numbers between 1 and n. Note that this method modifies the original array. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So, what can be do next.

Key Observation

If the array size is n, then missing integer should be between 1...n+1.

Why?

Lets take example - [1,2,4], len = 3; So, largest positive number in the worst case is 4, but that is present.So, missing number is 3. Take another example, [1,2,3], Now the missing number is 4. Take example, [1,3,4]. smallest missing number is 2. Take [2,3,4], smallest missing number is 1. Take [100, 112, 123], smallest missing number is 1.

Now Use Array as Hashtable

Lets assume if we can all array elements to hashset and iterate from from to 1...n+1 and see if number is missing. That is O(n+1) time and space. But what if we can use array has hashtable, we can save some space.

Though Process
  • We can map ith element to i-1th index in array. For eg. 1 is looked into index 0, n+1th element in nth index.
  • We can mark array element as -ve, if it exists in the array.
  • But array also has negative elements, how to handle it? Negative numbers are useless, as we want the positive number which is missing, so we can mark them to some special vlaue which will not affect the solution set. 0 is not a good candidate. Suppose we had -1 at index 2, and we market it 0. Then if we see 2 in array, we cannot make index 2 as negative. So, good candidate here is n+1, as it is just outside array length. And if we see it at the end, that is the answer need.
  • Now, once the array is ready, loop from 1...n+1 and see if that index is positve. If yest, that is the missing number.

Algo

  • Loop on array and mark negative integers as 0. We can also do for the integers larger than n.
  • Loop on array and mark k-1th index for integer k in range 1...n+1 in array negative
  • Loop from 1...n+1, and return first missing positive integer Code:
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    
    // 1. mark numbers (num < 0) and (num > n) with a special marker number (n+1) 
    // (we can ignore those because if all number are > n then we'll simply return 1)
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }
    // note: all number in the array are now positive, and on the range 1..n+1
    
    // 2. mark each cell appearing in the array, by converting the index for that number to negative
    for (int i = 0; i < n; i++) {
        int num = Math.abs(nums[i]);
        if (num > n) {
            continue;
        }
        num--; // -1 for zero index based array (so the number 1 will be at pos 0)
        if (nums[num] > 0) { // prevents double negative operations
            nums[num] = -1 * nums[num];
        }
    }
    
    // 3. find the first cell which isn't negative (doesn't appear in the array)
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            return i + 1;
        }
    }
    
    // 4. no positive numbers were found, which means the array contains all numbers 1..n
    return n + 1;
}