Find duplicate in array with a memory efficient approach

  • A+
Category:Languages

A is an array of integers.

All the values are between 0 to A.Length-1

it means 0 <= A[i] <= A.Length-1

I am supposed to find repeating elements; and if there are several repeating elements, then choose the one that has lower index for the repeated item.

for example:

a = [3, 4, 2, 5, 2, 3] 

then

result = 2 

This was an interview question. I used another array to store items and check when it is repeating. Then it gave me time-out for some test cases. The interviewee asked me to loop over the array only once, and do not create any additional list or variable.

 


No need for another data structure. You can use the input itself as a hashset.

Every time you see a value, add A.Length to the item that corresponds to that index. As values might have been already incremented, you should look at the value as A[i] mod A.length.

If you find an item that is already >= A.length.. you have a repetition. (Remember that the problem states that all items are in the interval [0, A.Length-1])

Track the lowest index that has been found as repeated.

This results in O(N) complexity (single pass) and no use of an additional data structure, i.e. Size O(1)

The key concept behind this approach is that hashsets work this way. Conceptually, this is indirectly related to the pigeonhole principle. https://en.wikipedia.org/wiki/Pigeonhole_principle

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: