Shohanur Rahman's blog

Count number of occurrences (or frequency) of each element in a sorted array

Shohanur Rahman's photo
Shohanur Rahman
·

4 min read

One algorithm that can be used to count the number of occurrences (or frequency) of each element in a sorted array is called the "Two Pointers" algorithm.

Here's how it works:

  1. Initialize two pointers, i and j, to the first element of the array.

  2. Compare the element at i with the element at j. If they are equal, increment the count for that element.

  3. If the element at j is different from the element at i, update the count for the element at i and move i to the next position.

  4. Repeat steps 2 and 3 until the end of the array is reached.

The time complexity of this algorithm is O(n) and space complexity O(1), where n is the number of elements in the array. This algorithm is efficient because it uses two pointers to iterate through the array, so it only needs to go through the array once, and it doesn't use any additional data structures to store the counts.

int[] arr = {1, 1, 1, 3, 3, 4, 5, 5, 6, 6};
int i = 0;
int j = 0;
int count = 0;

while (j < arr.length) {
    if (arr[i] == arr[j]) {
        count++;
        j++;
    } else {
        System.out.println(arr[i] + " occurs " + count + " times.");
        i = j;
        count = 0;
    }
}

// print the count for the last element
System.out.println(arr[i] + " occurs " + count + " times.");

In this example, the array arr is assumed to be sorted. The variable i and j are used as pointers, i points to the current element and j points to the next element. The variable count is used to store the number of occurrences of the current element. The while loop iterates through the array, comparing the element at i with the element at j. If they are equal, it increments the count, and if they are not equal, it prints the count for the current element and updates i and count to the next element.

It's important to note that the last element count will be missed if we don't print it after the while loop, so we print it separately.

Another efficient algorithm for counting the number of occurrences of each element in a sorted array is called "Counting by offset" algorithm.

Here's how it works:

  1. Initialize a variable count to 0 and a variable current to the first element of the array.

  2. Iterate through the array, starting at the second element.

  3. If the current element is equal to the previous element, increment the count.

  4. If the current element is different from the previous element, print the count and the previous element, then update current to the current element and reset the count to 1.

  5. Repeat steps 3 and 4 until the end of the array is reached.

  6. Print the count and the last element of the array.

The time complexity of this algorithm is O(n) and space complexity O(1) , where n is the number of elements in the array.

Here is an example implementation of this algorithm in Java:

int[] arr = {1, 1, 1, 3, 3, 4, 5, 5, 6, 6};
int count = 1;
int current = arr[0];

for (int i = 1; i < arr.length; i++) {
    if (arr[i] == current) {
        count++;
    } else {
        System.out.println(current + " occurs " + count + " times.");
        current = arr[i];
        count = 1;
    }
}

// print the count for the last element
System.out.println(current + " occurs " + count + " times.");

Another efficient algorithm for counting the number of occurrences of each element in a sorted array is called "HashMap" algorithm.

Here's how it works:

  1. Create an empty HashMap to store the element as key and its count as value.

  2. Iterate through the array, for each element, check if it already exists in the HashMap.

  3. If it exists, increment the count of that element in the HashMap.

  4. If it doesn't exist, add the element to the HashMap with count 1.

  5. Repeat steps 2-4 until the end of the array is reached.

  6. Print the count of each element in the HashMap.

The time complexity of this algorithm is O(n) where n is the number of elements in the array, space complexity is O(n) in the worst case where all elements in the array are distinct.

Here is an example implementation of this algorithm in Java:

int[] arr = {1, 1, 1, 3, 3, 4, 5, 5, 6, 6};
HashMap<Integer, Integer> countMap = new HashMap<>();

for (int i : arr) {
    if (countMap.containsKey(i)) {
        countMap.put(i, countMap.get(i) + 1);
    } else {
        countMap.put(i, 1);
    }
}

for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
    System.out.println(entry.getKey() + " occurs " + entry.getValue() + " times.");
}

This algorithm uses HashMap data structure to store the element as key and its count as value. It is efficient as it only iterates through the array once, and it doesn't need to keep track of the current element and its count separately like the previous algorithm. It's also worth noting that this algorithm works for both sorted and unsorted arrays.

Javainterview