Algorithms for Coding Interviews in C++/

...

/

Solution: Find Duplicates in Array

Solution: Find Duplicates in Array

Let's look at the various solutions to find the duplicates in an array

We'll cover the following...

Solution #1: Brute Force

Press + to interact
#include <iostream>
#include <vector>
using namespace std;
vector <int> findDuplicates(int arr[], int arrSize) {
  vector <int> duplicates;
  for(int i = 0; i < arrSize; i++) {
    for(int j = i+1; j < arrSize; j++) {
      if(arr[i] == arr[j] && i!=j)
        duplicates.push_back(arr[i]);
    }
  }
  return duplicates;
}
int main() {
  vector <int> output;
  int arr[] = {1, 3, 4, 3, 5, 4, 100, 100};
  int arrSize = 8;
  output = findDuplicates(arr, arrSize);
  if(!output.empty()) {
    for(std::vector<int>::iterator it = output.begin(); it != output.end()-1; ++it)
      cout << *it << ",";
    cout << *(output.end()-1);
  } else {
    cout << "No duplicates exist!" << endl;
  }
  
  cout << endl;
  int arr2[] = {1, 3, 3, 4, 3, 4, 100, 100};
  int arrSize2 = 8;
  output = findDuplicates(arr2, arrSize2);
  if(!output.empty()) {
    for(std::vector<int>::iterator it = output.begin(); it != output.end()-1; ++it)
      cout << *it << ",";
    cout << *(output.end()-1);
  } else {
    cout << "No duplicates exist!" << endl;
  }
}

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. If it is, then it will be added to the output vector—duplicates. However, when you have more than 2 copies of any given element, the element will be added to the vector as many times as it is present; this does not look great, as shown in the case of the array on line 30. 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 ...

Access this course and 1400+ top-rated courses and projects.