Here is the interview question prompt, presented for reference.
We're given an array of continuous numbers that should increment sequentially by
1, which just means that we expect a sequence like:
[1, 2, 3, 4, 5, 6, 7]
However, we notice that there are some missing numbers in the sequence.
[1, 2, 4, 5, 7]
Can you write a method
missingNumbers that takes an array of continuous numbers and returns the missing integers?
missingNumbers([1, 2, 4, 5, 7]); // [3, 6]
You can see the full challenge with visuals at this link.
Challenges • Asked over 3 years ago by Jake from AlgoDaily
This is the main discussion thread generated for Find Missing Number in Array.
I understand the code but have a question about how to describe the complexity.
Why is it correct to say it is O(N)? Is that in fact the best way to describe the complexity, or is there an alternate way to do so that captures the subtlety below? I've seen complexities described as O(k + n), for example, where there are 2 inputs. We don't have that in this case, but we do have O(lastvalue - firstval). I understand ultimately it will be linear but not proportional to array size.
In this case where the input is an array, an input of [10,50] is of course smaller than an input of [10,11,15,16,17,19,20].
To my understanding, normally where input is an array, when we say O(N) that would be input length.
Is it not more correct to specify this complexity as O(lastvalue - firstval), however one would say that.
Or am I overthinking.
I initially approached this problem a little different than the solution you provided. I knew that since the array was sorted the values within the list would have an interval range from the starting number in the array to the last number in the array. Therefore, I just looped through that range and checked whether or not the current num in the loop is not in the array. If it wasnt, that means its a missing number.
In your opinion does this solution work, or does your solution in looking for the difference between each number in the array to be 1 more efficient?
def missing_numbers(num_arr): missing =  for num in range(num_arr, num_arr[-1]+1): if num not in num_arr: missing.append(num) return missing
Big O notation drops the factors -- as an example,
O(1/2 * N) and simplifies to
O(N). Expressions like
O(k + n) are more precise, but ultimately describe the same phenomenon of "the amount of work increasing at the same rate that the input increases".
Regarding your second question: "To my understanding, normally where input is an array, when we say O(N) that would be input length. Is it not more correct to specify this complexity as O(lastvalue - firstval), however one would say that" - I think you have the right idea (and I'd argue that
lastvalue - firstvalue simplifies to input length), but the
n doesn't actually equal the input. The
n means it's a 1-to-1 ratio, every
n (whether it's 1, 2, 3) units of input scales to the same unit of work. Revisit the big O complexity guide for more details!
Your solution works well too, but is a bit slower and I'd say
O(n^2) complexity. The reason being that
if num not in num_arr will linearly look through the range every time (which is an
O(n) operation itself). So you iterate once through the input array, and then at every iteration-- you're iterating through the range. Hope this helps!
In the final solution, since the missing array stores the values which can be at worst n - 2, then the Space Complexity would still be considered O(n)?
Yeah exactly-- we can remove the constant and simplify it to
O(n)-- the amount of space required scales linearly with the input array, regardless of what numbers actually missing.