algorithm to find missing values in an array .. in place?

Question

I had a job interview today in which I was given an array of size n and the objective was to find the missing values in the array.

Input:
arr = [9,7,1,3,4,2,5]
Output:
6, 8

The input arr contains elements only from 1 till n. Note that the array is not sorted.

I got the "naive" version of the program done quickly, but it was O(n²) time complexity. I came up with a solution using a hash table (Python dictionary in my case) with time and space complexity both as O(n).

But then, I was asked to do it in place with no extra space, like the extra arrays and dictionary space I used in the solutions mentioned above were not allowed.

Any ideas to do this in time-complexity O(n) and space complexity O(1).

• Abhinav Mathur: How many missing values would be there? Are the array elements within a range (for example, [1,n])?
• BitTickler: So sorting in place would be one way to do it. Or did they ask for O(n) + In-place?
• Mark McWiggins: just two in the sample data but I was asked to assume a lot of data for a more general solution
• Mark McWiggins: they asked for O(n)
• BitTickler: I muse, there should not be any duplicate values in the data, right?

Answer 1

It could have been a trick question, given that "array like this" is not a sufficient specification, allowing for short cuts. And without short cuts (which make assumptions on the values in the array or other restrictions), the problem should be of sorting complexity (O(n log n)).

[2,2,2,2,2,2,2] is also an array "like this"? Or
[2,-2,2,-2,1000] ?

Depending on the "like-this-ishness" of what they imagine, there might or might not be short cuts.

So maybe, this job interview question was about how you query for missing information/requirements.

Answer 2

Assumption: The array consists of only integers in range [1,n] (there could be no other way to solve this question for a random number of missing values in O(N) without extra space).
The algorithm would be as follows:

for i in range 1 to n:
 index = abs(array[i])
 if array[index]>0:
 array[index] *= -1
for i in range 1 to n:
 if array[i]>0:
 print(i)

We use a simple observation here: for each element in the array, we make the item at index element negative. Then, we traverse the array again and see if we get any positive values, which means that index was never modified. If the index wasn't modified, then it was one of the missing values, so we print it.

• dxiv: You are assuming an array of size n, while the one in OP's post has a size strictly smaller than that.
• BitTickler: My gut tells me, there could be cases where you index out of bounds. If in an Array of length n, there are missing values, it follows, that there must be values > n and thus you get invalid indices.
• Abhinav Mathur: @dxiv OP must've missed adding duplicates. Because an O(N) solution without a limit on the range is impossible
• dxiv: @AbhinavMathur Maybe, but only the OP can clarify that. As is now, this does not answer the question as posed, and it would be helpful to future readers if you made a note of that in the answer.
• BitTickler: @dxiv Thats what I pointed out in my comment. Especially in the "no duplicates" case, size(array) == n only if there are no missing values. Once values are missing, size(array) < n. With duplicates, on the other hand, there could be negating more than once and the whole check for positives would not be correct.