Java 2D Array - Detect Duplicate Values

Question

What is the easiest/simplest/most efficient way to detect if a 2D array has duplicate/repeating values?

e.g. 2D Array:

{{2, 17, 4, 5} {3, 2, 34 9}}

This matrix has multiple "2" values.

I want to set a boolean to true if this is the case.

Thanks in advance!

I'm aware that I can probably loop through the entire matrix for each number but that is like 4 loop statements. Seems inefficient to me. — Connor
– Connor, Commented Sep 10, 2013 at 0:09
Can you say something more about data in your array? Can one row contain duplicate values like {2,3,2,1}? — Pshemo
– Pshemo, Commented Sep 10, 2013 at 0:13

Daniel Kaplan · Accepted Answer · 2013-09-10 02:07:30Z

3

I think the best you can do here is O(n) because you won't know if the very last element is a duplicate until you check it. Here's an idea:

Have a Set of values. Iterate the 2d array and for each element do this:

if (!set.add(element))
   // a duplicate was found!

This works because Set.add returns "true if this set did not already contain the specified element"

edited Sep 10, 2013 at 2:07

answered Sep 10, 2013 at 0:13

Daniel Kaplan

68.4k60 gold badges274 silver badges413 bronze badges

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

5 Comments

Simon Forsberg Over a year ago

Wouldn't it be sufficient with a Set? if (set.contains(value)) then there's a duplicate, otherwise add the value to the set. (The fact that the standard HashSet implementation use an underlying HashMap is another matter...)

Connor Over a year ago

I'm a little confused where you got the "1". And it seems nice, but my issue is this is a "lab" for school so it has to use a 2D array.

Daniel Kaplan Over a year ago

@SimonAndréForsberg Yeah good point. That's a better solution

Simon Forsberg Over a year ago

@Connor You will have to loop through the array in one way or another. Our suggestion is that you add each value you encounter to a HashSet if it doesn't already exists in it - if it already exists in the set, well then you have found a duplicate.

Daniel Kaplan Over a year ago

@SimonAndréForsberg updated. My brain went to Map first because I was reminded of a similar interview question I asked where someone asked the quickest way to get the number of duplicates. A Set doesn't help with that.

Collectives™ on Stack Overflow

Java 2D Array - Detect Duplicate Values

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related