Sunday, April 22, 2018

Find Duplicate Elements in an Array Java Program

If you have to write a Java program to find duplicate elements in an array one option you have 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.

Another option to find duplicate elements in an array is to sort the array first and then compare the adjacent element in a loop. Since array is sorted so the repeated elements would be adjacent to each other so you don't need an inner loop to compare current element with all the elements of the array. Thus the time complexity of this solution is O(nlogn + n). Time required for sorting is O(nlogn) and iteration of the array requires O(n) time.

To further 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 where you iterate an array and try to add element to the HashSet, if adding an element to the 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, extra space used is O(N).

Let's see Java program to find duplicate elements in an array using all of the approaches discussed above.


Looping through unsorted Array and comparing elements to find duplicates

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 array and compares it with the current element.

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

Finding duplicate elements in a sorted Array

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

Output

Duplicate element found 1
Duplicate element found 19

Using HashSet to find duplicate elements in an array

In this solution to find duplicate elements in an array in Java, 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 Find Duplicate Elements in an Array Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. How to Iterate a HashMap of ArrayLists of String in Java
  2. How to Remove Duplicate Elements From an Array Java Program
  3. How to Find Common Elements Between Two Arrays Java Program
  4. Find Largest and Second Largest Number in Given Array Java Program
  5. How to convert Array to ArrayList in Java

You may also like-

  1. Zipping Files in Java
  2. Getting All The Schemas in a DB Java Program
  3. Difference between Array and ArrayList in Java
  4. Difference Between Abstract Class And Interface in Java
  5. ArrayBlockingQueue in Java Concurrency
  6. Why wait(), notify() and notifyAll() methods are in Object class
  7. ThreadLocal class in Java
  8. Ternary operator in Java