Count Occurrences in Sorted Array

Problem Statement: You are given a sorted array containing N integers and a number X, you have to find the occurrences of X in the given array.

Examples:

Example 1:
Input: N = 7,  X = 3 , array[] = {2, 2 , 3 , 3 , 3 , 3 , 4}
Output: 4
Explanation: 3 is occurring 4 times in 
the given array so it is our answer.

Example 2:
Input: N = 8,  X = 2 , array[] = {1, 1, 2, 2, 2, 2, 2, 3}
Output: 5
Explanation: 2 is occurring 5 times in the given array so it is our answer.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Using linear search

Approach:

The approach is simple. We will linearly search the entire array, and try to increase the counter whenever we get the target value in the array. Using a for loop that runs from 0 to n – 1, containing an if the condition that checks whether the value at that index equals target. If true then increase the counter, at last return the counter.

Code:

C++ Code

#include <iostream>

using namespace std;

int count(int arr[], int n, int x) {

  int k = 0;
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      k++;
    }
  }
  return k;
}

int main() {
  int n = 7;
  int x = 3;
  int arr[] = {2,2,3,3,3,3,4};
  int ans = count(arr, n, x);
  cout <<x<<" occurs "<<ans<<" times in the array" << endl;
}

Output: 3 occurs 4 times in the array

Time Complexity: O(N)

Space Complexity: O(1)

Java Code

import java.io.*;

class TUF {

  public static int count(int[] arr, int n, int x) {
    int k = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == x) {
        k++;
      }
    }
    return k;

  }

  public static void main(String[] args) {
    int n = 7;
    int x = 3;
    int[] arr = {2,2,3,3,3,3,4};
      
    int ans = count(arr, n, x);
    System.out.println(x+" occurs "+ans+" times in the array");
  }
}

Output: 3 occurs 4 times in the array

Time Complexity: O(N)

Space Complexity: O(1)

Solution 2: Using Binary search

Approach: This approach uses Binary Search to find the index of the X. Then checks the left and right half of the array for getting more occurrences of X.

Call a function that uses Binary search to determine the index of the X in the array, and return the index.

Now we must check for the first occurrences of X at the left and right half of the array.

Increase the counter if X exists at the left and right half of the array. At last return the counter.

Code:

C++ Code

#include <iostream>

#include <iostream>

using namespace std;

int binary(int arr[], int n, int x) {
  int s = 0;
  int e = n - 1;

  while (s <= e) {
    int m = (s + e) / 2;

    if (arr[m] == x) {
      return m;
    } else if (arr[m] < x) {
      s = m + 1;
    } else {
      e = m - 1;
    }
  }
  return -1;
}

int count(int arr[], int n, int x) {
  // code here
  // get the index of X in array
  int idx = binary(arr, n, x);

  // if X does not exist return 0;
  if (idx == -1) {
    return 0;
  }

  int k = 1;
  int left = idx - 1;

  // check left half for X
  while (left >= 0 && arr[left] == x) {
    k++;
    left--;
  }
  // check right half for X
  int right = idx + 1;
  while (right < n && arr[right] == x) {
    k++;
    right++;
  }

  return k;
}

int main() {
  int n = 7;
  int x = 3;
  int arr[] = {2,2,3,3,3,3,4};
    
  int ans = count(arr, n, x);
  cout <<x<<" occurs "<<ans<<" times in the array" << endl;
}

Output: 3 occurs 4 times in the array

Time Complexity: O(logN)

Space Complexity: O(1)

Java Code

import java.io.*;

class TUF {
  public static int binary(int[] arr, int n, int x) {

    int s = 0;
    int e = arr.length - 1;

    while (s <= e) {
      int m = (s + e) / 2;

      if (arr[m] == x) {
        return m;
      } else if (arr[m] < x) {
        s = m + 1;
      } else {
        e = m - 1;
      }
    }
    return -1;

  }
  public static int count(int[] arr, int n, int x) {

    // code here
    // get the index of X in array
    int idx = binary(arr, n, x);

    // if X does not exist return 0;
    if (idx == -1) {
      return 0;
    }

    int k = 1;
    int left = idx - 1;

    // check left half for X
    while (left >= 0 && arr[left] == x) {
      k++;
      left--;
    }
    // check right half for X
    int right = idx + 1;
    while (right < n && arr[right] == x) {
      k++;
      right++;
    }

    return k;

  }

  public static void main(String[] args) {
    int n = 7;
    int x = 3;
    int[] arr = {2,2,3,3,3,3,4};
     
    int ans = count(arr, n, x);

    System.out.println(x+" occurs "+ans+" times in the array");
  }
}

Output: 3 occurs 4 times in the array

Time Complexity: O(logN)

Space Complexity: O(1)

Special thanks to Rushikesh Yadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article