Design a linear time algorithm for finding the least positive integer missing from an unsorted array. Changes in the array are allowed.
For example, for the array -10,-1,2,3,6,30, the answer is 1.
I thought about finding the maximum and minimum numbers in the array (this is $\Theta(n)$), then a loop from the minimum number to the maximum number, and in every iteration, check if the current number is in the array, but this will take $\Theta(n^2)$.
You could do radix sort with counting sort if your input matches the criteria for these algorithms (this is O(n) ). Another way would be creating a vector of bool the size of the input. Initialize all elements to false. Once you encounter a positive integer, set the index of this positive integer to true if it is within the bounds of the vector size. Once this is done you can traverse this vector and the first false value you find is the least positive integer missing.
Hint (if extra memory is allowed): It is enough to determine which of the elements $1,\ldots,n$ are in the input array. Using an auxiliary array, you can accomplish this in $O(n)$.
Try to rearrange the array so that it starts with the numbers 1 to n, as far as possible, that is a [i] = i + 1 for 0 ≤ i < n. To do this: Loop for 0 ≤ i < n. As long as 1 ≤ a [i] ≤ n and a [a [i] - 1] != a [i] exchange a [i] and a [a [i] - 1].
This works in O (n) because you loop through n values, and you store at most n values into their right place.
Then you just check which is the first i such that a [i] ≠ i+1, and i+1 is the first missing number. If none are found missing, then n+1 is the first missing number.
