CODEWITHSUNDEEP
arraysalgorithm
ditoslav
ditoslav

Reputation: 4872

How to check if there are two identical objects in a 2d array

So I have an array and I want to know whether there are two identical elements.

My first thought was of a O(n^2) algorithm where I compare each element with all the others but of course it's not optimal.

My second thought was of sorting the array and then just comparing the neighbouring elements but it doesn't sound like the perfect solution.

I guess I can only dream of O(n) but is there a faster way in at least O(n*log(n)) to do it? (Of course, I would very much appretiate an O(n) solution.

EDIT: I have to do this as a part of a more complex algorithm so I am going to have to make a new array and get the answer n*log(n) times so I don't feel like hashing.

Upvotes: 0

Views: 85

Answers (1)

amit
amit

Reputation: 178431

This is basically the element distinctness problem, which cannot be solved better than O(nlogn), unless you are exploiting a hashing solution with addition space.

Upvotes: 4

Related Questions