2

Possible Duplicate:
Find the Smallest Integer Not in a List

I got asked this question in an interview

Given an unsorted array, find the smallest number that is missing. Assume that all numbers are postive.

input = {4,2,1,3,678,3432}

output = 5

Sorting it was my first approach. Second approach of mine is to have a boolean flag array.The second approach takes up lots of space.

Is there any other better approach than this ?

Community
  • 1
  • 1
user2434
  • 6,339
  • 18
  • 63
  • 87
  • Another approach would be to use a min heap. Construct min heap from the given numbers. Start with counter=1. Delete the element i.e. 1. elementDeleted==Counter. Increment counter continue with deletion of second element 2. Again counter==elemetnDeleted. continue till counter!=elementDeleted – Sandeep Mar 18 '15 at 20:39

2 Answers2

9

Suppose the length of the given array is N. You can go with the boolean-flag approach, but you don't need to take numbers that are larger than N into account, since they're obviously too big to affect the answer. You could also consider a bitmap to save some space.

unkulunkulu
  • 11,576
  • 2
  • 31
  • 49
  • +1 This is also as good as one can get - the time complexity is O(N) and the memory complexity is O(N). I do not think there is a better solution. – Ivaylo Strandjev Jun 22 '12 at 12:57
  • @izomorphius, there's a very interesting answer in the linked question in the comments. – unkulunkulu Jun 22 '12 at 13:07
  • I had an answer using bucket sort but worst case that requires infite memory. This is a better solution. – acattle Jun 22 '12 at 18:12
  • @acattle, really consider checking out the answers to the question that is linked in the comments by Luchian Grigore, a copy of my answer is there too, but there is also a better solution in certain circumstances (actually the answer being looked for by the interviewers I believe) – unkulunkulu Jun 22 '12 at 18:59
0

An alternative solution to unkulunkulu's is the following:

k := 1
Make an array of 2^k booleans, all initially set to false
For every value, V, in the array:
  if V < 2^k then:
    set the V'th boolean to true
Scan through the booleans, if there are any falses then the lowest one indicates the lowest missing value.
If there were no falses then increment k and go to step 2.

This will run in O(n log s) time and O(s) space, where n is the size of the input array and s is the smallest value not present. It can be made more efficient by not rechecking the lowest values on successive iterations, but that doesn't change the constraints.

Running Wild
  • 2,951
  • 18
  • 15