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).

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

BitTickler · Accepted Answer · 2021-03-26 05:15:32Z

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.

answered Mar 26, 2021 at 5:15

BitTickler

12.1k6 gold badges37 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Abhinav Mathur · Accepted Answer · 2021-03-26 05:00:52Z

0

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.

answered Mar 26, 2021 at 5:00

Abhinav Mathur

8,2363 gold badges14 silver badges26 bronze badges

8 Comments

dxiv Over a year ago

You are assuming an array of size n, while the one in OP's post has a size strictly smaller than that.

BitTickler Over a year ago

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 Over a year ago

@dxiv OP must've missed adding duplicates. Because an O(N) solution without a limit on the range is impossible

dxiv Over a year ago

@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 Over a year ago

@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.

|

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related