Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Count Element Occurrence

Explore three methods to count the occurrences of an element in an array, including brute force and binary search techniques. Understand their respective time complexities and how to apply them to optimize solutions for searching and counting in sorted arrays.

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 ...