Linear time algorithm for least positive integer missing from array 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)$.
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)$.