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