Find Duplicate Element In Array

| 3 | 6 | 8 | 8 | 10 | 12 | 15 | 15 | 15 | 20 |
  0   1   2   3    4    5    6    7    8    9

1. Finding duplicates in sorted array

• For finding duplicates we first need to scan through the list, using the number of length of the array.
• Take a counter, i, which will check if the next element in the array is identical. When it is found, store it in a lastDuplicate variable and move on.
• We need to think of cases where there are more than two duplicates in a row: our function should not print several duplicates in a row.

void dupsortedarray(int A[]) {
  int n = 10;
  int lastDuplicate = 0;

  for (int i = 0; i < n - 1; i++) {
    if (A[i] == A[i + 1] && A[i] != lastDuplicate) {
      printf("%d\n", A[i]);
      lastDuplicate = A[i];
    }
  }
}

2. Counting duplicates in sorted array

• Similar to the last procedure, but we also have to count how many times it's appearing (with a variable j for example)

void countdups(int A[]) {
  int n = 10;
  int j = 0;

  for (int i = 0; i < n - 1; i++) {
    if (A[i] == A[i + 1]) {
      j = i + 1;

      while (A[j] == A[i]) {
        j++;
      }
      printf("%d is appearing %d times\n", A[i], j - i);
      i = j - 1;
    }
  }
}

3. Finding duplicates in sorted array using hashing

• Use a second array filled with zeros again, this time the array size is 20, since 20 is the largest element.
• Scan through the array, take one index at a time using an index pointer.
• Once again, incrementing in an array filled with zeros only takes constant time.

void dupshashing(int A[]) {
  int n = 10;
  int m = 20;
  int H[21] = {0};

  for (int i = 0; i < n; i++) {
    H[A[i]]++;
  }

  for (int i = 0; i <= m; i++) {
    if (H[i] > 1) {
      printf("%d %d\n", i, H[i]);
    }
  }
}

4. Finding duplicates in unsorted array

| 8 | 3 | 6 | 4 | 6 | 5 | 6 | 8 | 2 | 7 |
  0   1   2   3   4   5   6   7   8   9

There can be more than one solution.

• First solution: scan through an array, pick up an element and look for its duplicate, by checking if it is present in the rest of the array.
• This is going to be an O(n²) algorithm.

void dupunsorted(int *B) {
  int n = 10;
  for (int i = 0; i < n - 1; i++) {
    int count = 1;

    if (B[i] != -1) {
      for (int j = i + 1; j < n; j++) {
        if (B[i] == B[j]) {
          count++;
          B[j] = -1;
        }
      }
    }

    if (count > 1) {
      printf("%d %d\n", B[i], count);
    }
  }
}

4. Finding duplicates in unsorted array using hashing

• Once again, hashing allows us to traverse the array only once, adding to an array filled with zero is still in constant time.

void dupunsortedhashing(int B[]) {
  int n = 10;
  int m = 9;
  int H[9] = {0};

  for (int i = 0; i < n; i++) {
    H[B[i]]++;
  }

  for (int i = 0; i <= m; i++) {
    if (H[i] > 1) {
      printf("%d %d\n", i, H[i]);
    }
  }
}