Find duplicates in java list

Duplicate elements in a list means the elements which occur more than once.
In this article, we will understand different ways to achieve this including those added in java 8.

1. Using Set
Below is the algorithm for this method to find duplicate elements in a list in java.

Create a new java Set object and a new arraylist to hold duplicate elements.
Iterate or loop through the list.
For each element in the list, add it to the Set using its add() method.
add() returns true, if the element is added and false, if the element was already present in the set.
Therefore, if the element is already in the Set, it is a duplicate.
So, we add it to the arraylist.
At the end of the iteration, the duplicate arraylist will contain all duplicate elements in the original list.

Example program based on this algorithm is as below

List<Integer> numbers = List.of(1, 2, 3, 4, 3, 1, 2);
Set<Integer> set = new HashSet<>();
List<Object> duplicates = new ArrayList<>();
numbers.forEach(n -> {
  if (!set.add(n)) {
    duplicates.add(n);
  }
});
System.out.println("Duplicate elements: " + duplicates);

Output is

Duplicate elements: [3, 1, 2]

Note that we have used java 8 forEach() method to iterate over the list but you can use any other way as well.
2. Using Map
Below are the steps of algorithm for this method.

Create a new map object and a new arraylist to hold duplicate elements.
Keys of this map will be the elements of the original list and its values will be the count of their occurrence in the list.
Loop through the list.
For each element in the list, check if it exists as a key in the Map using its containsKey() method.
If it exists, increment its value in the Map and add it again using put() method.
If it does not exist, add it to the Map with a value of 1.
After the list iteration is complete, all the map elements with a value greater than 1 are duplicates.
Finally, iterate over the map and add those elements whose value is greater than 1 to the list for holding duplicate elements.

Example program is as below

List<Integer> numbers = List.of(1, 2, 3, 4, 3, 1, 2);
Map<Integer, Integer> countMap = new HashMap<>();
List<Object> duplicates = new ArrayList<>();
numbers.forEach(n -> {
  if (countMap.containsKey(n)) {
    countMap.put(n, countMap.get(n) + 1);
  } else {
    countMap.put(n, 1);
  }
});
countMap.keySet().forEach(k -> {
  if(countMap.get(k)> 1) {
    duplicates.add(k);
  }
});

3. Using nested loops
If you are asked to find duplicate elements in a list without using any Collection classes such as Set or Map etc., then this method would be useful.
Algorithmic steps for this method are

Loop through the list.
For each element in the list, loop through the rest of the list.
If the current loop element is equal to any of the remaining elements, it is a duplicate.

Program written as per these steps is as follows

List<Integer> numbers = List.of(1, 2, 3, 4, 3, 1, 2);
List<Object> duplicates = new ArrayList<>();
for (int i = 0; i < numbers.size() - 1; i++) {
  for (int j = i + 1; j < numbers.size(); j++) {
    if (numbers.get(i).equals(numbers.get(j))) {
      duplicates.add(numbers.get(i));
    }
  }
}

4. Using java 8 streams
This method is based on java 8 streams and works on the below steps.

Convert the list to a stream.
Convert the stream to a Map using collect() method such as the key is each element in the list and value is the number of occurrences.
collect() method returns a Map and accepts a Collector as argument. Implementation of Collector determines the keys and values of the resultant Map.
In this case, since we want the Map keys to be the list elements and its values to be the count of their occurrence, we can use Collectors.groupingBy() to create a collector.
Once the Map is created with groupingBy(), use the entrySet() method to get a set of Map.Entry objects.
Filter the entries based on the value (that is, number of occurrences) greater than 1.
Map the filtered entries to their keys.

Example program is

List<Integer> numbers = List.of(1, 2, 3, 4, 3, 1, 2);
Map<Object, Long> map = numbers.
                        stream().
                        collect(
                          Collectors.
                          groupingBy(n -> n, Collectors.counting())
                        );
List<Object> duplicates = map.
                          entrySet().
                          stream().
                          filter(e -> e.getValue() > 1).
                          map(e -> e.getKey()).
        collect(Collectors.toList());

groupingBy() is used to group elements of a collection based on some criteria.
Here’s how the groupingBy() method works for this example:

The criteria is supplied as a Lambda expression since groupingBy() accepts a Function argument, which is a functional interface.
In this case, we are grouping by the identity function n -> n, which means we are grouping the elements of the list by their values.
The second argument to groupingBy() is another collector that specifies how the elements in each group should be combined.
In this case, we are using Collectors.counting(), which creates a Map that contains the count of each element in the list.

So, the resulting map will contain a count of how many times each element appears in the list.

We are then filter this map to find the elements that have a count greater than 1, which indicates that they are duplicates using filter() method.

Hope the article was useful.

Find duplicates in list in java

Find duplicates in java list