Algorithms for Coding Interviews in C++/

...

/

Solution: Count Element Occurrence

Solution: Count Element Occurrence

Here is a detailed analysis of the different ways to count the frequency of a number in a sorted array of integers

We'll cover the following...
C++
#include <iostream>
using namespace std;
int calcFreq(int arr[], int arrSize, int s) {
  int count = 0;
  for(int i = 0; i < arrSize; i++) {
    if(arr[i] == s)
      count++;
  }
  return count;
}
int main() {
  int arr[] = {-5,-3,0,1,3,3,3,3,4,5};
  cout << calcFreq(arr, 10, 3) << endl;
}

This is an extremely simple way to solve this problem. We simply initialize a variable to keep count called, count to 0 and then iterate over the array, increasing count by 1 every time the target value is encountered.

Time Complexity

The time complexity of this algorithm is in O(n)O(n) since the array is iterated over once.

Solution #2: Using Binary Search

C++
#include <iostream>
using namespace std;
int calcFreq(int arr[], int arrSize, int s) {
  int index = binarySearch(s, arr, arrSize);
  
  if (index == -1)   // If element is not present 
    return 0; 
  int count = 1; // Initialzing a count
  
  int start = index - 1; // Counting the ones present on the left
  while (start >= 0 && arr[start] == s) {
    count++;
    start--; // Decrement the start index if found
  }
  
  int end = index + 1;  // Counting the ones present on the right
  while (end < arrSize && arr[end] == s) {
    count++;
    end++; // Increment the end index if found
  }
  
  return count; 
}
int main() {
  int arr[] = {-5,-3,0,1,3,3,3,3,4,5};
  cout << calcFreq(arr, 10, 3) << endl;
}

This is also a very simple solution. It draws upon the fact that if an element exists in a sorted array, all of its occurrences exist contiguously. It ...