Finding Duplicates in an Unsorted Array Using Counter and Adjacent Element Comparison

Finding duplicates in an unsorted array is a common task. A naive approach involves nested loops that compare each element with every other element, but this is inefficient (O(n^2)). Another way combines the use of counters with sorting the array first, so that duplicates become adjacent. Then, you can compare adjacent elements to identify duplicates (O(n log n)).

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] array = {4, 2, 1, 2, 5, 3, 4};
    Arrays.sort(array);
    
    for (int i = 0; i < array.length - 1; i++) {
      if (array[i] == array[i + 1]) {
        System.out.println("Duplicate found: " + array[i]);
      }
    }
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>

int main() {
  int array[] = {4, 2, 1, 2, 5, 3, 4};
  int length = sizeof(array) / sizeof(array[0]);
  
  std::sort(array, array + length);
  
  for (int i = 0; i < length - 1; i++) {
    if (array[i] == array[i + 1]) {
      std::cout << "Duplicate found: " << array[i] << std::endl;
    }
  }
  
  return 0;
}

Python

1
2
3
4
5
6
array = [4, 2, 1, 2, 5, 3, 4]
array.sort()

for i in range(len(array) - 1):
    if array[i] == array[i + 1]:
        print(f"Duplicate found: {array[i]}")

Key Takeaways

Sorting the unsorted array brings duplicates together, making them adjacent.
Once sorted, a single loop is used to compare adjacent elements for identifying duplicates.
This technique has a time complexity of O(n log n), better than the naive approach of O(n^2).