Missing number(s) Interview Question Redux

Question

The common interview problem of determining the missing value in a range from 1 to N has been done a thousand times over. Variations include 2 missing values up to K missing values.

Example problem: Range [1,10] (1 2 4 5 7 8 9 10) = {3,6}

Here is an example of the various solutions:

Easy interview question got harder: given numbers 1..100, find the missing number(s)

My question is that seeing as the simple case of one missing value is of O(n) complexity and that the complexity of the larger cases converge at roughly something larger than O(nlogn):

Couldn't it just be easier to answer the question by saying sort (mergesort) the range and iterate over it observing the missing elements?

This solution should take no more than O(nlogn) and is capable of solving the problem for ranges other than 1-to-N such as 10-to-1000 or -100 to +100 etc...

Is there any reason to believe that the given solutions in the above SO link will be better than the sorting based solution for larger number of missing values?

Note: It seems a lot of the common solutions to this problem, assume an only number theoretic approach. If one is being asked such a question in an S/E interview wouldn't it be prudent to use a more computer science/algorithmic approach, assuming the approach is on par with the number theoretic solution's complexity...

More related links:

Sorting or using BitSets are perfectly valid solutions unless the interviewer explicitly specifies that he is looking for a streaming algorithm or that the set requires too much memory. — abc
What if you don't even have O(N) memory available? What if you have to implement this on an embedded device with very limited resources, and the input comes in the form of a stream with no random access? — gcbenison
The problem with this answer is the OP posted this in questions that specifically require O(K) space only; whereas this answer requires O(N) space. The OP characterized the other answers (some of which are quite good) as "ridiculous answers". — WestCoastProjects
The problems make the most sense, when the input is given in a streaming sense: You can't actually store all n items in memory, but they are shown to you one at a time. You only have k^O(1) memory to play with. In this case the sum-of-powers technique makes sense. You can also improve the "time used per number shown", by hashing as in stackoverflow.com/a/36851791/205521 — Thomas Ahle
@javadba, the original question did ask for O(k) space complexity, but heap sort can manage the problem in O(1) space. — Elliott

Matthieu M. Matthieu M. · Accepted Answer · 2010-12-10T09:27:44

You are only specifying the time complexity, but the space complexity is also important to consider.

The problem complexity can be specified in term of N (the length of the range) and K (the number of missing elements).

In the question you link, the solution of using equations is O(K) in space (or perhaps a bit more ?), as you need one equation per unknown value.

There is also the preservation point: may you alter the list of known elements ? In a number of cases this is undesirable, in which case any solution involving reordering the elements, or consuming them, must first make a copy, O(N-K) in space.

I cannot see faster than a linear solution: you need to read all known elements (N-K) and output all unknown elements (K). Therefore you cannot get better than O(N) in time.

Let us break down the solutions

Destroying, O(N) space, O(N log N) time: in-place sort
Preserving, O(K) space ?, O(N log N) time: equation system
Preserving, O(N) space, O(N) time: counting sort

Personally, though I find the equation system solution clever, I would probably use either of the sorting solutions. Let's face it: they are much simpler to code, especially the counting sort one!

And as far as time goes, in a real execution, I think the "counting sort" would beat all other solutions hands down.

Note: the counting sort does not require the range to be [0, X), any range will do, as any finite range can be transposed to the [0, X) form by a simple translation.

EDIT:

Changed the sort to O(N), one needs to have all the elements available to sort them.

Having had some time to think about the problem, I also have another solution to propose. As noted, when N grows (dramatically) the space required might explode. However, if K is small, then we could change our representation of the list, using intervals:

{4, 5, 3, 1, 7}

can be represented as

[1,1] U [3,5] U [7,7]

In the average case, maintaining a sorted list of intervals is much less costly than maintaining a sorted list of elements, and it's as easy to deduce the missing numbers too.

The time complexity is easy: O(N log N), after all it's basically an insertion sort.

Of course what's really interesting is that there is no need to actually store the list, thus you can feed it with a stream to the algorithm.

On the other hand, I have quite a hard time figuring out the average space complexity. The "final" space occupied is O(K) (at most K+1 intervals), but during the construction there will be much more missing intervals as we introduce the elements in no particular order.

The worst case is easy enough: N/2 intervals (think odd vs even numbers). I cannot however figure out the average case though. My gut feeling is telling me it should be better than O(N), but I am not that trusting.

Missing number(s) Interview Question Redux

8 Answers