Home » Technical Interview Questions » Array Interview Questions » Count Number of Occurrences in a Sorted Array

Count Number of Occurrences in a Sorted Array


Reading Time - 6 mins

In the given sorted array, Count number of occurrences or frequency in a sorted array of X where X is an integer.

Example

Input

13

1 2 2 2 2 3 3 3 4 4 4 5 5

3

Output

3

Approach 1 for Count Number of Occurrences in a Sorted Array

1. Simply do a modified binary search such that
2. Find the first occurrence of X like this:

  1.  Check if the middle element of the array is equal to X.
  2. If the equal or greater element is at mid then reduce the partition from start to mid-1. As we will have the first occurrence on the left side of mid of array then.
  3. If the middle element is smaller then we will check in the right side of the middle element as the array is sorted.
  4. Return the first occurrence.

3. Now similarly find the last occurrence of X in the array by doing

  1. Check if the middle element of the array is equal to X
  2. If the equal or smaller element is at mid then increase the partition from mid+1 to high. As we will have the last occurrence on the right side of mid of array then.
  3. Else search in the left side of array
  4. return the last occurrence
READ  Valid Triangle Number

4. Now the number of occurrences is simply the last occurrence – first occurrence+1.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int first_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int first = INT_MAX;
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found then check the left part for further occurence
    {
      if(mid < first)
      first = mid;
      high = mid-1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return first;
}
int last_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int last = INT_MIN;
  
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found check in right subpart for last occurence
    {
      if(mid > last)
      last = mid;
      low = mid+1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return last;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int X; // number whose count is to be found out
  cin >> X;
  int count = 0; //initially its count is zero
  int last = last_occurence(a,n,X);
  if(last != INT_MIN)
    count += last;
  
  int first = first_occurence(a,n,X);
  if(first != INT_MAX)
    count -= first;
  cout<<last-first+1<<endl;  
  return 0;
}
8
1 1 2 2 2 3 4 5 
2
3

Approach 2 for Count Number of Occurrences in a Sorted Array

  1. Simply do the same approach as algorithm 1 but using upper_bound() and lower_bound functions.
  2. Calculate the last occurrence using upper_bound() and first occurrence via lower_bound() functions.
  3. Number of occurrences is simply the index obtained by upper_bound() –
  4. lower_bound().

Low_bound(), Upper_bound are Standard Template Library(STL) functions.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    count  = upper_bound(a,a+n,X) - lower_bound(a,a+n,X); 
    cout<<count;
    return 0;
}
8
1 1 2 2 2 3 4 5 
4
1

Complexity Analysis for Count Number of Occurrences in a Sorted Array

Time Complexity – O(logN) where N is the size of the array. Here we use inbuild STL function which has logN time complexity.
Space Complexity – O(1) because we don’t use any auxiliary space here.

Approach 3 for Count Number of Occurrences in a Sorted Array

  1. Simply run a loop.
  2. If we get an element equal to X start increasing the count
  3. Till we see X increase the count and as soon as we get a number different from X then we display the obtained count as it is a sorted array.

Explanation

Run one loop from beginning to the end of the array and check for if x==a[i] then increase the counts. Here let’s take an example. a[]={1, 2, 2, 2, 3, 4} and x=2 then the count of x is 3. So, our final answer is 3.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    for(int i=0;i<n;i++)
    if(a[i]==X)
      count++;
    cout<<count;
    return 0;
}
8
1 1 2 2 2 3 4 5 
1
2

READ  Last Stone Weight

Complexity Analysis for Count Number of Occurrences in a Sorted Array

Time Complexity – O(N) because we traverse the whole array and count the frequency of x.
Space Complexity – O(1) because we don’t use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions