Interview Questions

Find all duplicates in an array in linear time (v1)

This is a common interview question where you need to write a program to find all duplicates in an array where the numbers in the array are in the range of 0 to n-1 where n is the size of the array. For example: [1, 2, 3, 3] is okay but [1, 2, 6, 3] is not. In this version of the challenge there can be multiple duplicate numbers as well.
The algorithm below is commented to explain what each piece of code does, but the general algorithm is:
(1) Loop through the array
(2) For each element, find array[absolute(array[i])] in the array and set its value to negative if positive
(3) If in step 2 you encounter a negative number, then it means the element at index i in the array is a duplicate
## An example

You need to be a premium member to see the rest of this question and code.

mrdaniel
published this on 11/11/15 **|**

2

Since JavaScript has the concept of -0, the code can be significanlty simplified. The test for -0 is 1/x > 0. Evaluates to false if x is -0 and true if normal +0.

var abs = (x) => Math.abs(arr[x]); for (var i = 0; i < arr.length; i++) { // get element in array var el = arr[abs(i)]; // element in array is positive so make it negative; handle -0 if (el >= 0 && 1/el > 0) arr[abs(i)] = -arr[abs(i)]; // element is negative so it is a duplicate else dups.push(Math.abs(arr[i])); }

numbergames

commented on 09/28/16

1

@numbergames
Don't see how to edit, but need to update the test in my code -- don't need two tests, so

if (el >= 0 && 1/el > 0)should be:

if (1/el > 0)

numbergames

commented on 09/28/16

1

@karn09 This specific solution solves the challenges of finding duplicates in an array with numbers *only* in the range 0 to n-1 where n is the size of the array.
So for [1,2,1,3,6, 5] it wouldn't work because the size of the array is 6 so the range must be 0 to 5, and there is a 6 in the array. Same goes for the second example.
The v2 algorithm gives a solution for the more general challenge of finding duplicates in an array of any range of numbers.

mrdaniel

commented on 03/14/16

0

Sorry I just realized this was building up to using a hash table.

camsbury

commented on 06/18/16

0

I did this using a hash table in Python - seems to still run in O(n) time (and with less array manipulation), and works for any numbers:

def get_dups(array): ht = {} dups = [] for x in array: if x in ht: dups.append(x) else: ht[x] = x return list(set(dups))

camsbury

commented on 06/18/16

0

Very good point. I will need to be more careful when reading over the cases. Thank you.

karn09

commented on 03/15/16

0

There seems to be a problem with this solution. In certain cases it returns a duplicate multiple times and in others will return non-duplicated numbers.
duplicates([1,2,1,3,6, 5]); => [1,0]
duplicates([0,2,1,3,6, 6]); => [0,0]
I think part of the issue is with setting the special case 0 to be equal to the length where arrays contain duplicates that are equal to the length.

karn09

commented on 03/14/16

Login to submit a comment