Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Find Duplicates in Array

Let's look at the various solutions for finding the duplicates in an array.

We'll cover the following...

Solution #1: Brute force

Java
class Duplicates {
 public static ArrayList < Integer > findDuplicates(int arr[]) {
  int arrSize = arr.length;
  ArrayList < Integer > duplicates = new ArrayList < Integer > ();
  for (int i = 0; i < arrSize; i++) {
   for (int j = i + 1; j < arrSize; j++) {
    if (arr[i] == arr[j] && i != j)
     duplicates.add(arr[i]);
   }
  }
  return duplicates;
 }
 public static void main(String[] args) {
  int arr[] = {
   7,
   5,
   4,
   3,
   5,
   11,
   7,
   11,
   3,
   11
  };
  ArrayList < Integer > dupes = findDuplicates(arr);
  System.out.println("Duplicates in " + Arrays.toString(arr) + " are " + dupes);
  int arr1[] = {
   6,
   5,
   17,
   17
  };
  dupes = findDuplicates(arr1);
  System.out.println("Duplicates in " + Arrays.toString(arr1) + " are " + dupes);
 }
}

This solution iterates over the input array for each given element, starting from the element after the given element, and checks if another element is equal to it or not (lines 6-8). If it is equal, then it is added to the output list —duplicates (line 9). However, when you have more than 2 copies of any given element, the element is added to the ArrayList as many times as it is present. This does not look great, as shown in the case of the array on line 25 (11 occurs thrice in the output). We can check if the element has already been counted, as in solution # 2.

Time complexity

The array is iterated once for each element present so the time complexity is in O(n2 ...