# 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)$$.

• You can solve this in $O(n\log n)$ by sorting the array, which is already better than your $O(n^2)$. Dec 12, 2016 at 20:11

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.

• This is the same as my answer, with a few more details added. Dec 13, 2016 at 10:15
• The sorting method is disjoint from your answer. The original poster appeared to be working through this problem without success from your answer so I added more details Dec 13, 2016 at 10:19
• Since this is a homework exercise, some of us in this community believe that it is best not to provide full answers, for many different reasons (see this discussion). Of course, the suitable level of hints is very subjective. Dec 13, 2016 at 10:22
• Oh no I'm sorry again Yuval. I'm new to the community so I just began answering questions quickly without thinking about whether or not the question was a homework question or not. I just now read through a meta community standards doc Dec 13, 2016 at 10:28
• This time both your answer and mine are in the gray zone, so I suggest you keep it, and be mindful in the future. Dec 13, 2016 at 10:29

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)$.

• shalom yuval. sorry your hint didnt help me, can you please post a more helpful hint? Dec 12, 2016 at 21:50
• Unfortunately it is customary here not to provide full solutions to homework problems. This hint will have to do for now. Dec 12, 2016 at 21:54
• I've implemented it and Yuval's solution seems to do the trick. Dec 12, 2016 at 23:05
• can you post an example for what you wrote please or explain it more? 1,..,n is the array's elements? or number one to the end of the array? what to do with the auxiliary array? I dont understand what you wrote Dec 13, 2016 at 6:41
• It's not a solution, it's a hint. You have to work it out. Dec 13, 2016 at 6:41

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.