2

This is a slightly modified version of a well known problem, but I can't seem to figure this one out.

We are given an array of size n that contains unsorted sequence of positive numbers with no duplicates. I'm trying to find the smallest positive number that is not contained in the array, but I can't sort or edit the array in any way. The whole thing should be in O(nlogn) time and O(logn) space complexity.

All the solutions I can think of are in polynomial time complexity.

mathew7k5b
  • 137
  • 2
  • 10
  • Possible duplicate of [Easy interview question got harder: given numbers 1..100, find the missing number(s)](http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe) – OneCricketeer Nov 08 '16 at 23:59
  • Just scan the array and update the minimum if encountering number less than the current minimum. O(n) time and O(1) space – SomeWittyUsername Nov 09 '16 at 00:02
  • 1
    @SomeWittyUsername Maybe read the question more carefully. – Kittsil Nov 09 '16 at 00:36

1 Answers1

10

You can solve this without modifying the array by binary searching on the answer. Remember that we are looking for the smallest positive integer that is not in the array. This means the answer can't be larger than n + 1 since we only have n numbers in our array. So we just need to binary search between 1 and n + 1 to find our answer.

Within our binary search, we want to answer the question: for a given number k, is every integer 1 through k contained in our array? Because there are no duplicates, we can solve this by just counting the number of elements in the array less than or equal to k. If the count is k, every such integer is in our array; otherwise, at least one is missing.

So we binary search to find the smallest value of k where the above property is false. The binary search requires O(log n) iterations, and each iteration takes O(n) time for a total of O(n log n) time. The space is actually O(1) since all we need is a single variable for counting.

Neal
  • 912
  • 8
  • 14
  • Binary search requires the array to be sorted – Gonen I Nov 09 '16 at 00:09
  • 2
    Right, but we aren't binary searching the array. We're binary searching on the eventual answer. – Neal Nov 09 '16 at 00:10
  • So you scan the array once to find the largest and smallest numbers, then binary search between them? – Gonen I Nov 09 '16 at 00:16
  • No, you only need to binary search between 1 and n + 1, which are guaranteed bounds on the answer. – Neal Nov 09 '16 at 00:20
  • Aren't you making assumptions that aren't in the problem statement? How can you fairly assume the range of values is 1 to n+1? – Daniel Williams Nov 09 '16 at 00:30
  • 1
    I didn't assume the range of values is 1 to n + 1. I claimed that the answer will always be between 1 and n + 1. – Neal Nov 09 '16 at 00:32
  • But all the numbers could be much larger than n – Gonen I Nov 09 '16 at 00:35
  • That's fine--it doesn't make the algorithm invalid if there are very large numbers in our array. All we need to know is that the final answer will not be greater than n + 1, which is always true. – Neal Nov 09 '16 at 00:36