Find missing numbers in array, time complexity O(N), space complexity O(1)

Question

You are given an array of n unique integer numbers 0 <= x_i < 2 * n. Print all integers 0 <= x < 2 * n that are not present in this array.

Example:

find_missing([0]) = [1]

find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]

find_missing([]) = []

find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]

Quirks are about requirements:

Time complexity O(n) - BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.

Space complexity O(1) - you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t).

I saw a lot of complex solutions, but then I found this:

public void printNotInArr(int[] arr) {
    if(arr == null)
        return null;

    int len = arr.length;
    int max = 2 * len;

    for(int i = 0; i < len; i++) {
        System.out.println(max - arr[i] - 1);
    }
}

I believe that is the best solution, but I am not sure. I would like to know why that would NOT work.

Since it doesn't do what you asked for, it is not a solution at all. Try passing in `0, 3`. You'll get `3, 0` back, clearly it doesn't output the missing numbers at all. — Lasse V. Karlsen, Apr 10 '16 at 17:13
Is the input guaranteed to be sorted, like it is in all the examples? — Joni, Apr 10 '16 at 17:19
Is this the same as this question, https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe ? — גלעד ברקן, Apr 10 '16 at 17:23
It is not the same as that question, גלעד ברקן, as that other question only removed one number. That is a completely different question with an easy solution. This one here is different, where multiple numbers can be missing. The easy solution for that other question does not work here. — Lasse V. Karlsen, Apr 10 '16 at 17:32
I see now that it breaks if two elements complement each other. I.E. if Max = 3, arr=[0, 3] 0+3 = 3 = Max. arr=[1,2] -> rs[2,1] and 2+1 = 3. — , Apr 10 '16 at 18:00
Two local variables would be considered as O(1) space, so just use one for index and one for next expected value in the array, and make a single pass through the array. — rcgldr, Apr 10 '16 at 18:05
@LasseV.Karlsen Read the question more carefully - the OP generalizes the problem, as does the accepted answer. https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe — גלעד ברקן, Apr 10 '16 at 19:09

Vaughn Cato · Accepted Answer · 2016-04-10T20:15:29.977

As @LasseV.Karlsen pointed out, [0,3] is a simple counter-example that shows how that solution doesn't work. This, however, is a pretty simple solution (in Python):

def show_missing(l):
  n = len(l)

  # put numbers less than n into the proper slot
  for i in range(0,n):
    while l[i]<n and l[i]!=i:
      j = l[i]
      l[i] = l[j]
      l[j] = j
  for i in range(0,n):
    if l[i]!=i:
      print('Missing %s'%i)

  # put numbers greater than n into the proper slot
  for i in range(0,n):
    while l[i]>=n and l[i]!=i+n:
      j = l[i]
      l[i] = l[j-n]
      l[j-n] = j
  for i in range(0,n):
    if l[i]!=i+n:
      print('Missing %s'%(i+n))

The idea is simple. We first rearrange the elements so that every value j that is less than n is stored at index j. We can then go through the array and easily pick out the ones below n that are missing.

We then rearrange the elements so that every value j that is greater than or equal to n is stored at index j-n. Again, we can go through the array and easily pick out the ones greater than or equal to n that are missing.

Since only a couple of local variables are used, the O(1) space complexity is satisfied.

Because of the nested loops, the O(n) time complexity is a little harder to see, but it isn't too hard to show that we never swap more than n elements, since one new element is put into its proper place with each swap.

Since we've only swapped elements of the array, the requirement that all the original elements are still in the array is also satisfied.

Can you explain why you first do numbers less than N, then numbers bigger than N? and in second loop, why "l[i]!=i+n" and not "l[i]!=i" — , Apr 10 '16 at 20:25
@user117325: We can't do both the larger and the smaller numbers at the same time because there would be conflicts. For example if l==[0,2]. — Vaughn Cato, Apr 10 '16 at 20:28
@user117325: In the second loop we are only considering values >= n. `n` is stored at index 0, `n+1` is stored at index 1, etc. So that's why we're checking to see if `l[i]!=l[i+n]`. — Vaughn Cato, Apr 10 '16 at 20:32
The code by @YvesDaoust (above) does the same thing regarding the O(n) swap, but does not do it into two parts (less than N, bigger than N). Is there another example that would cause the conflict you describe? His solution might be missing that — , Apr 10 '16 at 21:19
@user117325: I don't think that answer is valid, since it relies on extending the original array. — Vaughn Cato, Apr 10 '16 at 21:34

Find missing numbers in array, time complexity O(N), space complexity O(1)

1 Answers1