Generate list of remaining numbers

Question

Given a number n, and an array with size m where m<n. Provided that each number in the array is between 0 and n-1 (inclusive), I want to get as efficiently as possible the list of n-m numbers from 0 to n-1 which aren't in the array.

That's how I'm doing it (in pseudocode), but it feels rather inefficient and I'm wondering if there's a better way:

int[] remaining (int[] assigned) {
    Set<int> s
    int[n-m] remaining
    add each int in assigned to s
    for(i = 0 to n-1) 
        if(not s.contains(i)) remaining.add(i);
}

This isn't any particular computer language but it should be ilustrative. We'll assume that accessing an array is of course O(1) and adding/checking a set is O(log(n)) as an AVL set would be. So basically I'm trying to get this in linear time, instead of O(n·logn) like it's now, but if the initial array isn't sorted I don't know how to go about it, or if it's even possible.

Answer 1

copy the array into a hashmap H. This takes O(m).

for i from 0 to n-1
    if(H.ispresent(i) == FALSE)
        output i

This for loop takes O(n). As n>=m the overall complexity is O(n)