Counting Duplicates in a Sorted Array

Counting duplicates in a sorted array involves identifying and tallying the repeated elements. Given that the array is sorted, duplicates are guaranteed to be adjacent, making it easier to count them. You can loop through the array comparing adjacent elements. When a duplicate is found, you increase a counter until a new element appears.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {
  public static void main(String[] args) {
    int[] array = {1, 2, 2, 3, 4, 4, 4, 5};
    int counter = 1;
    
    for (int i = 0; i < array.length - 1; i++) {
      if (array[i] == array[i + 1]) {
        counter++;
      } else {
        if (counter > 1) {
          System.out.println("Element " + array[i] + " appears " + counter + " times.");
        }
        counter = 1;
      }
    }
    // Handle last element
    if (counter > 1) {
      System.out.println("Element " + array[array.length - 1] + " appears " + counter + " times.");
    }
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

int main() {
  int array[] = {1, 2, 2, 3, 4, 4, 4, 5};
  int length = sizeof(array) / sizeof(array[0]);
  int counter = 1;
  
  for (int i = 0; i < length - 1; i++) {
    if (array[i] == array[i + 1]) {
      counter++;
    } else {
      if (counter > 1) {
        cout << "Element " << array[i] << " appears " << counter << " times." << endl;
      }
      counter = 1;
    }
  }
  // Handle last element
  if (counter > 1) {
    cout << "Element " << array[length - 1] << " appears " << counter << " times." << endl;
  }
  
  return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
array = [1, 2, 2, 3, 4, 4, 4, 5]
counter = 1

for i in range(len(array) - 1):
    if array[i] == array[i + 1]:
        counter += 1
    else:
        if counter > 1:
            print(f"Element {array[i]} appears {counter} times.")
        counter = 1
# Handle last element
if counter > 1:
    print(f"Element {array[-1]} appears {counter} times.")

Key Takeaways

Because the array is sorted, duplicates are adjacent.
A single loop can be used to both identify and count duplicates.
A counter variable is used to tally each set of duplicates. Reset the counter when a new element is encountered.