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!

• Connor: 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.
• Pshemo: Can you say something more about data in your array? Can one row contain duplicate values like {2,3,2,1}?
• Connor: No. No duplicates at all in the matrix.

Answer 1

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"

• Simon Forsberg: 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: 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: @SimonAndréForsberg Yeah good point. That's a better solution
• Simon Forsberg: @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: @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.