First Missing Positive Number

Photo by Possessed Photography on Unsplash

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

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

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Algorithm:

The basic idea is that we have an array with n cells (n is the length of the array). If an integer is missing it must be in the range [1..n]. This is the crucial observation we use to deduce the algorithm. This means that the range of possible answers is [1..n] if an integer is missing, and if an integer is not missing then the answer is n+1.

Let’s picture the only two possibilities:

1. there is no missing integer in the array
2. there is a missing integer in the array.

If there is no missing integer, this means that the array has all number from 1 to n. This must mean that the array is full. Why, because in the range [1..n] there are exactly n numbers, and if you place n numbers in an array of length n, the array is by definition full. (in this case solution is to return n+1 which is the first smallest integer).

Once you understand the first case above understanding the second is easy. If there is a missing integer (or more than one), the missing integer(s), let’s call it X, must be in the range 1..n. Why, because if the missing integer X is not in the range [1..n] that would imply that all integers [1..n] are in the array, which would mean that the array is full, leaving no space where to place X (since X is not in the range [1..n]).

Then the algorithm becomes:

1- Ignore all numbers <=0 and >n since they are outside the range of possible answers (which we proved was [1..n]). We do this by replacing them with the value 1.
2- For all other integers <n+1, mark their bucket (cell) to indicate the integer exists(change the existing positive to negative).
3- Find the first cell not marked, that is the first missing integer. If you did not find an unmarked cell, there was no missing integer, so return n+1.

Solution

Complexity

Runtime: O(N)

Space: O(1)