Friday, 14 October 2016

Finding duplicate elements in an array - Java Program

If you have to find duplicate elements in an array first thing you will think is to loop through the array taking one element at a time and then compare it with all the other elements of the array in order to find the duplicates. Though this solution works fine but the problem here is you are looping though the array twice making the time complexity of this solution O(n2). Because of the double iteration program will be slow.

Thus to minimize the execution time you can think of using a data structure like HashSet which will reduce the time complexity to O(n). Since Set doesn't allow duplicate elements trying to do that will return false. So you can have a logic when ever adding an element to a HashSet returns false that means a duplicate element. As I said since array is iterated only once so time complexity is O(n) here but a new data structure is created, apart from array you are also creating a Set, so space complexity increases here. Space complexity is O(n2) for this solution.

Looping through Array and comparing elements

Here you have an outer loop that iterates the array one element at a time and another loop that starts from the next element and iterates through all the elements of the element and compares.

public class DuplicateArrayElement {

    public static void main(String[] args) {
        int[] numArray = {2, 6, 7, 6, 2, 19, 1, 19};
        for(int i = 0; i < numArray.length; i++){
            for(int j = i + 1; j < numArray.length; j++){
                if(numArray[i] == numArray[j]){
                    System.out.println("Duplicate element found " + numArray[j]);
                }
            }
        }    
    }
}

Output

Duplicate element found 2
Duplicate element found 6
Duplicate element found 19

Using HashSet

Here iteration of the array is done and elements of the array are added to the set.

Here thing to understand is - If set already contains the element, call to add method of the set leaves the set unchanged and returns false.
So, whenever false is returned that means a duplicate element.

public class DuplicateArrayElement {

    public static void main(String[] args) {
        int[] numArray = {2, 6, 7, 6, 2, 19, 1, 19};
        Set<Integer> numSet = new HashSet<Integer>();
        for(int num : numArray){
            // If add returns false
            if(!numSet.add(num)){
                System.out.println("Duplicate element found " + num);
            }
        }
    }
}

Output

Duplicate element found 2
Duplicate element found 6
Duplicate element found 19

That's all for this topic Finding duplicate elements in an array - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How to iterate a Hash map of arraylists of String in Java?
  2. How to Sort elements in different order in TreeSet
  3. How to convert Array to ArrayList in Java
  4. Difference between Array and ArrayList in Java

You may also like -

>>>Go to Java Programs page

No comments:

Post a Comment