Daily bit(e) of C++ | Smallest missing positive integer
Daily bit(e) of C++ #9, Common interview question: Smallest missing positive integer
Today, we will look at a common interview question - The smallest missing positive integer.
Given a list of integers, determine the smallest missing positive integer. Importantly your solution must run in O(n) time, and while you are permitted to modify the input, you can only use constant additional memory.
As an example, for the input {3, -1, 0, 4, 1}, the smallest missing positive number is 2, for the input {1, 2, 3}, the smallest missing positive number is 4.
Before you continue to read the solution, try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/G7r4rebhd.
Solution
The trivial solution would be sorting our input. However, that would be O(n*logn) time complexity.
Although, this is not a completely wrong direction to explore.
Crucially, our missing number must be in the range [1, N+1], and it will only be N+1 if the input contains all numbers in the range [1, N]. We also do not care about duplicates.
These two points allow us to formulate a simpler quasi-sort because we know the destination index of each of the numbers in the range [1, N]; it is the range of indexes [0, N-1].
We can, in one pass, iterate over our input, putting each number in the correct place.
Then, to determine which number is missing, we again iterate over the input and return the missing number, or N+1, if we finish iterating over the input without finding any.
