Find duplicate element occur more than two times from an array in java

Question

I want to find out the duplicate element and there index number from an array. I write down a code for that. It works well but only fail to generate exact output when number of duplicate element more than 2. I read the value from a file and then build an array and then searching duplicate element from this array.

import java.io.File;
import java.util.Arrays;
import java.util.Scanner;

public class T1 {
public static void main(String args[]) throws Exception{
    Scanner x=new Scanner(new File("C:\\Duplicate_array.txt"));
    int [] duplicate_data=new int[9];
    int i1=0;
    while(x.hasNext()){
        int a=x.nextInt();
        duplicate_data[i1]=a;
        i1++;
    }
    System.out.println(Arrays.toString(duplicate_data));
    for (int i = 0; i < duplicate_data.length-1; i++) {
        for (int j = i+1; j < duplicate_data.length; j++) {
            if ((duplicate_data[i] == duplicate_data[j]) && (i != j)) {
                System.out.println("Duplicate Element : "+duplicate_data[j]);
                System.out.println("Index of that duplicate element : "+j);
            }
        }
    }
}
}

Here is my output:

[5, 6, 1, 6, 9, 5, 2, 1, 5]
Duplicate Element : 5
Index of that duplicate element : 5
Duplicate Element : 5
Index of that duplicate element : 8
Duplicate Element : 6
Index of that duplicate element : 3
Duplicate Element : 1
Index of that duplicate element : 7
Duplicate Element : 5
Index of that duplicate element : 8

Error at last line.It already find 5 at the beginning at position no: 8. But at the end of the program it again searching for 5 and give the position no. This last search is unnecessary. How to get rid of this last search?

Are you allowed to use a `Set` in your algorithm or do you need to use plain arrays only? — Mick Mnemonic, Jul 24 '18 at 14:53

score 3 · Answer 1 · answered Jul 24 '18 at 15:01

(i != j) is not necessary in your if statement, since j is always ahead of i by 1, but that's not your issue.

You could try using a duplicate array flag to know when you've already found a duplicate.

import java.util.Arrays;

public class StackOverflow {
    public static void main(String args[]) throws Exception {
        int[] duplicate_data = {5,6,1,6,9,5,2,1,5};
        boolean[] duplicate = new boolean[duplicate_data.length];

        System.out.println(Arrays.toString(duplicate_data));
        for (int i = 0; i < duplicate_data.length - 1; i++) {
            for (int j = i + 1; j < duplicate_data.length; j++) {
                // Make sure you haven't flagged this as a duplicate already
                if (!duplicate[j] && duplicate_data[i] == duplicate_data[j]) {
                    duplicate[j] = true;
                    System.out.println("Duplicate Element : " + duplicate_data[j]);
                    System.out.println("Index of that duplicate element : " + j);
                }
            }
        }
    }
}

Result:

[5, 6, 1, 6, 9, 5, 2, 1, 5]
Duplicate Element : 5
Index of that duplicate element : 5
Duplicate Element : 5
Index of that duplicate element : 8
Duplicate Element : 6
Index of that duplicate element : 3
Duplicate Element : 1
Index of that duplicate element : 7

Abdel Hady Mohamed · Answer 2 · 2018-07-25T16:08:23.380

It is searching for the same duplicates again because you are not storing previously found duplicates by any means. So, You have to use a data structure to store previously found duplicates and not searching for them again. This takes us to a better solution for finding duplicates which is using a hashset from the beginning because it's O(n) instead of O(n^2)

import java.io.File;
import java.util.Arrays;
import java.util.Scanner;

public class T1 {
    public static void main(String args[]) throws Exception {
        Scanner x=new Scanner(new File("C:\\Duplicate_array.txt"));
        Set<Integer> set = new HashSet<Integer>();
        int index = 0;
        while(x.hasNext()){
            int nextNumber = x.nextInt();
            if (set.contains(nextNumber)) {
                System.out.println("Duplicate Element : " + nextNumber);
                System.out.println("Index of that duplicate element : "+index); 
            } else
                set.add(nextNumber);
        }
    }
}

As you can see, when using the HashSet, we didn't need the two nested for loops. We can test if a HashSet contains a number in constant time O(1) which eliminates the need for searching the whole array element by element to find the duplicate.

Keep in mind that worst case for `HashSet` or any hash implementation that only the average case is `O(1)`. Worst case is `O(lg(n))` for Java 8 and `O(n)` for Java 7. See: https://stackoverflow.com/a/51199917/5065400 for more details. For small sizes, this is a trivial point, but one to be aware of. — Randomness Slayer, Jul 24 '18 at 15:08

score 2 · Accepted Answer · answered Jul 24 '18 at 15:01

You want to iterate through your array only one time. If all you want is duplicates, you can do this simply by keeping track of any value you have seen before using an ArrayList:

int[] data = {5, 6, 1, 6, 9, 5, 2, 1, 5};

System.out.println(Arrays.toString(data));

ArrayList<Integer> seenBeforeList = new ArrayList<>();
for(int index = 0; index < data.length; index++){
    int value = data[index];
    if(seenBeforeList.contains(value)){
        System.out.println("Duplicate Element : " + value);
        System.out.println("Index of that duplicate element : " + index);
    } else {
        seenBeforeList.add(value);
    }
}

Output:

[5, 6, 1, 6, 9, 5, 2, 1, 5]
Duplicate Element : 6
Index of that duplicate element : 3
Duplicate Element : 5
Index of that duplicate element : 5
Duplicate Element : 1
Index of that duplicate element : 7
Duplicate Element : 5
Index of that duplicate element : 8

If you want to group by value, then it would make more sense to use a HashMap, storing the value as the key, and the indexes as the value. Then simply iterate through the HashMap.

score -1 · Answer 4 · answered Jul 24 '18 at 14:45

i starts at 0 (value 5) and j starts at the end of the array(value 5) it outputs the the position of duplicate right. However when I is at the end of array and j starts at the end it will do the same thing, to solve this you can make a copy of the array and when traversing the array delete the dulpicate items.

Find duplicate element occur more than two times from an array in java

4 Answers4