How to find duplicate elements in an array of an array?

Question

Possible Duplicate:
Java Array, Finding Duplicates

I have this array

int[][] array = {{1,2,3,4}, {5,6,2,8}, {9, 10, 11, 12}, {13, 14, 15, 16}};

If there are duplicate elements in this array, i need to return false. For example index [0][1] and [1][2] are equal. I need a method that detects this. Also it would be nice if the solution only used primitives, arrays, and loops.

@Natix and Tomas -- Guys don't make fun of him, help him instead of discouraging to resolve his issue. — Smit, Dec 13 '12 at 20:49

score 5 · Answer 1 · answered Dec 13 '12 at 20:31

5

1: Add all values to a List (e.g ArrayList)
2: add all to a set (e.g TreeSet)

compare list.size() to set.size()

if not equal, than you have dupplicates

answered Dec 13 '12 at 20:31

AlexWien

28,470
6
53
83

1

Beated me to it by a few secs. As a comment, to avoid adding everything you can do a single loop to add the elements from the list to the set and return `true` (meaning "there are duplicates") if `theSet.add()` return false. – Fritz Dec 13 '12 at 20:38
1

@AlexWien, Its really nice way to resolve issue. But take a look at his code, do you really think he will be able to do this. – Smit Dec 13 '12 at 20:39
Why do you even need step 1, this solution doesn't take advantage of early exiting – durron597 Dec 13 '12 at 20:40
1

@Gamb the set.add() method would be the answer I'd vote up. The first instance where it returns false could be the stopping condition. no need for the list at all. – David Dec 13 '12 at 20:42
1

I would just add them to a set and skip the list. ;) – Peter Lawrey Dec 13 '12 at 20:43
@PeterLawrey seriously, it makes me angry that this has this many upvotes – durron597 Dec 13 '12 at 20:44
@PeterLawrey using external libraies is not the ideal solution, except for millions of entries. – AlexWien Dec 13 '12 at 20:51

score 4 · Accepted Answer · answered Dec 13 '12 at 20:42

4

If you only want to use primitives you can use TIntHashSet like this

TIntHashSet set = new TintHashSet(); // like Set<Integer> but with primitives
for(int[] arr: array) for(int i: arr) if(!set.add(i)) return false;
return true;

The set.add method returns false if the value could not be added as it's a duplicate.

answered Dec 13 '12 at 20:42

Peter Lawrey

525,659
79
751
1,130

2

[`TIntHashSet`](http://trove4j.sourceforge.net/javadocs/gnu/trove/set/hash/TIntHashSet.html) is a primitive? Do I have the right link? – durron597 Dec 13 '12 at 20:45
Nice, but a solution using an external library is not the way to go, except for 1 million entries. – AlexWien Dec 13 '12 at 20:50
TInHashSet is not a primitive nor is the int[] it wraps but it avoid creating Integers or Entry objects like HashSet would. I agree that a plain `HashSet` should be considered first. – Peter Lawrey Dec 13 '12 at 21:05
2

Thanks for the solution. I've modified it a little bit so as to not use an external library. I changed: `TIntHashSet set = new TintHashSet();` to: `Set set = new HashSet();` – abandoned Dec 13 '12 at 23:48

Smit · Answer 3 · 2012-12-13T20:44:39.370

1

I think its a homework question, so no actual implementation only guidelines.

You need 2 for loops only as you have 2D array.
Iterate through all numbers in your array and compare them for their equality.
If any duplicate found return false.

Another way

Convert this 2D array to 1D array
Iterate and compare all values

edited Dec 13 '12 at 20:44

answered Dec 13 '12 at 20:34

Smit

4,685
1
24
28

This does not work. You need to pick the first index and compare it to every other. Then pick then pick the second and compare it to every other again, and so on... This simply would not work with 2 loops. – abandoned Dec 13 '12 at 20:39
@user1253722 I updated the answer will this help you or not let me know? – Smit Dec 13 '12 at 20:45

score 1 · Answer 4 · answered Dec 14 '12 at 06:38

Try below code

package com.rais.duplicates;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Rais.Alam
 * @date Dec 14, 2012
 */
public class DetectDuplicateClient
{

    public static boolean isDuplicate(int[][] array)
    {
        boolean retVal = false;
        if (array != null && array.length > 0)
        {
            Set<Integer> temp = new HashSet<Integer>();

            outer:
            for (int[] innerArray : array)
            {
                for (int value : innerArray)
                {
                    if(!temp.add(value))
                    {
                        retVal = true;
                        break outer;
                    }

                }
            }
        }
        return retVal;
    }

    public static void main(String[] args)
    {

        int[][] array =  { { 1, 2, 3, 4 }, { 5, 6, 2, 8 }, { 9, 10, 11, 12 },{ 13, 14, 15, 16 } };

        System.out.println(isDuplicate(array));
    }

}

durron597 · Answer 5 · 2012-12-13T20:47:52.713

Pseudocode:

Loop through all values, adding them to a HashSet
At each iteration, check to see if the Set contains that element. If it does, return false immediately.
return true;.

Here's another way that works only if you know the maximum element

Create a new array, where each cell in the array is indexed by the element
If the array cell is zero, increment the cell (cell[element]++).
If the array cell is 1, return false;.
return true;

score 0 · Answer 6 · answered Dec 13 '12 at 21:17

0

My solution:

2D array elements to a list
Sort the list
Check in one for loop if i indexed list item == i + 1

answered Dec 13 '12 at 21:17

Laszlo Papp

84
1
6

How to find duplicate elements in an array of an array?

6 Answers6