2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ You can solve this in $O(n\log n)$ by sorting the array, which is already better than your $O(n^2)$. $\endgroup$ – Yuval Filmus Dec 12 '16 at 20:11
  • $\begingroup$ this might help you ideone.com/fXNJl0 $\endgroup$ – Daniel Dec 13 '16 at 13:41
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is the same as my answer, with a few more details added. $\endgroup$ – Yuval Filmus Dec 13 '16 at 10:15
  • $\begingroup$ 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 $\endgroup$ – Logan Leland Dec 13 '16 at 10:19
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 13 '16 at 10:22
  • $\begingroup$ 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 $\endgroup$ – Logan Leland Dec 13 '16 at 10:28
  • $\begingroup$ This time both your answer and mine are in the gray zone, so I suggest you keep it, and be mindful in the future. $\endgroup$ – Yuval Filmus Dec 13 '16 at 10:29
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ shalom yuval. sorry your hint didnt help me, can you please post a more helpful hint? $\endgroup$ – Ginger Dec 12 '16 at 21:50
  • 2
    $\begingroup$ Unfortunately it is customary here not to provide full solutions to homework problems. This hint will have to do for now. $\endgroup$ – Yuval Filmus Dec 12 '16 at 21:54
  • $\begingroup$ I've implemented it and Yuval's solution seems to do the trick. $\endgroup$ – Aristu Dec 12 '16 at 23:05
  • $\begingroup$ 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 $\endgroup$ – Ginger Dec 13 '16 at 6:41
  • $\begingroup$ It's not a solution, it's a hint. You have to work it out. $\endgroup$ – Yuval Filmus Dec 13 '16 at 6:41
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.