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)$. Commented Dec 12, 2016 at 20:11
• this might help you ideone.com/fXNJl0 Commented Dec 13, 2016 at 13:41

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. Commented 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 Commented 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. Commented 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 Commented 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. Commented 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? Commented 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. Commented Dec 12, 2016 at 21:54
• I've implemented it and Yuval's solution seems to do the trick. Commented 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 Commented Dec 13, 2016 at 6:41
• It's not a solution, it's a hint. You have to work it out. Commented 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.