2

Possible Duplicate:
Find the Smallest Integer Not in a List

An interview question. given a unsorted int array. How to find first int that bigger than 0 and not appears in that given array. for example:

input :[1,2,0]   
output: 3

input [2,4,-1,1]  
output: ３

I gave two solution

a) sort.  Time C is: O(n), space C is O(1)  
b) bitmap. Time Complexity :O(n), space O(n)

But interviewer doesn't satisfied. he said there is Time O(n) and constant space solution.

Any thought?

The resource is from my online friend.

Community
  • 1
  • 1
user658266
  • 2,397
  • 4
  • 20
  • 14
  • input [2,4,-1,1] output: 2. Are you sure the answer is 2 and not 3? – Phonon Mar 21 '11 at 21:39
  • 1. Are you sure, input [2,4,-1,1] yields output 2? Shouldn't it be 3? 2. Good sorting algorithms are O(n*log(n)), not O(n). 3. O(1) is constant space. – Oswald Mar 21 '11 at 21:43
  • Is the answer to the 2nd example correct - should it be 3? – Mick Mar 21 '11 at 21:43

0 Answers0