Finding the first missing number given the list with numbers [reviewed]

Problem

Given input [2,3,1,5,88,100], find the first missing number. All number are positive numbers. (1 - n)

In the above example, 4 is the first missing number.

Brute force approach $O(N \log_2 N)$

Simplest way is to sort the numbers in the array $O(N \log_2 N)$, and scan from the beginning to fin d the first missing numbers. $O(N)$.

This is not ideal since there might be a way to do it in O(N).

Sequential scanning using HashTable Time complexity $O(N)$,  space complexity $O(N)$.

Better way is to scan the list and put all the numbers in the hash table. Also remember the max value, M while scanning. 

Then, start from 1 until M check if which number does not exists. First number that is not exist will be the first missing number.

Now, we cut the running time to $O(N)$. However, there might be a way to bring the space complexity to $O(1)$

Sequential scanning using swapping Time complexity $O(N)$,  space complexity $O(1)$.

One important fact about numbers in this array is this:

- All the numbers are positive number and we just need to find the first missing number.

Imagine we have all the positive numbers in ascending order without gap in the array. It will like below:

If there is not missing numbers, the value at position i, should be i + 1 !!

Now, what we need to do is two folds:

1. scan the numbers in the list. For swap value n, with the value in n-1 position if n -1 < N, where N is the number of input.

2. scan from the beginning and check if the value at the current position, i is equals to i + 1. If not, i+1 is missing !!

Overall, run time of this algorithm is $O(N)$ and space complexity is $O(1)$ !!

Here is the algorithm in python. 

Practice statistics:

Did not come up with this algorithm during the interview. I only came up with the second algorithm. 

7:00: to write up the code.

1:29: to fix up the bugs (did not return i+1 as a missing number)