Find duplicate elements in an Array in Java

There are many ways to find duplicate elements in an array in Java. Here, we will cover the most used ones.

Find duplicate elements

We can find duplicates by iterating using two loops, inner and outer. We also need to make sure we are not comparing element with itself. Depending on the number of elements in the array, this way of comparing elements can have a very high time complexity (O (n ^ 2)). 

Example

class FindDuplicateElements {

  public static void main(String[] args) {

    int[] array = new int[]{2, 4, 7, 2, 11, 5, 7, 14, 22, 11, 49, 58, 14, 101, 1, 3, 205, 49, 101, 12};

    for (int i = 0; i < array.length; i++) { // outer loop
      for (int j = i + 1; j < array.length; j++) { // inner loop
        if (i != j && array[i] == array[j]) {
          System.out.println("Duplicate element found:" + array[i]);
        }
      }
    }

  }
}
Duplicate element found:2 Duplicate element found:7 Duplicate element found:11 Duplicate element found:14 Duplicate element found:49 Duplicate element found:101
 
In this way, if we have one element more than twice, we will get multiple outputs for the same element.

We can avoid that using the list. Let’s try it.

class FindDuplicateElements {

  public static void main(String[] args) {

    int[] array = new int[]{2, 4, 7, 2, 11, 17, 2, 19, 7, 22, 7, 49};
    List<Integer> duplicates = new ArrayList<>();

    for (int i = 0; i < array.length; i++) {
      for (int j = i + 1; j < array.length; j++) {
        if (i != j && array[i] == array[j] && !duplicates.contains(array[i])) {
          duplicates.add(array[i]);
        }
      }
    }

    System.out.println("Duplicate elements: ");
    System.out.println(duplicates);

  }
}
Duplicate elements: [2, 7]
 
Here, when we find a duplicate for the first time, we are adding that element to a list, and we need to add one more check inside if block to check does the list contains the element. If yes, ignore, otherwise add it to the List.

Using a Set

Set in Java is a Collection that can’t contain duplicates. In this example, we will iterate over array of strings and add each element to a set. If the element is already present in the set, it will be ignored.

class FindDuplicateElements {

  public static void main(String[] args) {

    String[] array = new String[]{"Megan", "Tom", "Mellisa", "Tom", "John", "Megan"};
    Set<String> set = new HashSet<>();

    for (String element : array) {
      if (!set.add(element)) {
        System.out.println("Duplicate element found: " + element);
      }
    }

  }
}
Output: Duplicate element found: Tom Duplicate element found: Megan
 
You can also use a list to avoid printing the same elements more than once. This way of finding duplicates has a much lower time complexity since we are using only one loop.

Find duplicate elements in an Array using Streams

In this example, we will use Streams API introduced in Java 8 to check for the frequency of the elements, and if the element is found more than once, it will be added to a set.

class FindDuplicateElements {

  public static void main(String[] args) {

    String[] array = new String[]{"London", "Paris", "Amsterdam", "London", "New York", "Paris"};

    Set<String> set = Arrays.stream(array).filter(i -> Collections.frequency(Arrays.asList(array), i) > 1).collect(Collectors.toSet());

    System.out.println(set);

  }
}
Output: [London, Paris]
 
That’s it!

Leave a Reply

Your email address will not be published.