Count Occurrences in Sorted Array
Srivastava Bodakunti
0
55
Problem: Given a sorted array and an element x, we need to count occurrences of x in the array.
Examples:
Input:arr[] = {10, 20, 20, 20, 30, 30}, x = 20
Output: 3
Input: arr[] = {10, 10, 10, 10, 10}, x = 10
Output: 5
Input: arr[] = {5, 8, 10}, x = 7
Output: 0Naive solution is to traverse array linearly by maintaining count for the given element which has a time complexity of O(n)
Efficient solution is to make use of two Binary Search (Index of First Occurrence + Index of Last Occurrence) implementations which has a time complexity O(log n) for each which is equal to O(log n)
Here are the links implementations for Index of First and Last Occurence:
Index of First Occurrence in Sorted Array
Index of Last Occurrence in Sorted Array
Solution:
/**
* <p><b>Count Occurrences:</b> is to count occurrences of given element in an array or list</p>
* <p><b>Time Complexity:</b> O(log n)</p>
* <p><b>Usage:</b></p>
* {@code
* int[] countOccNums = {10, 10, 20, 30};
* CountOccurrences.of(countOccNums, 10)
* }
*/
public class CountOccurrences {
/**
* <b>FLow:</b>
* <p>Make use of two Binary Search (Index of First Occurrence + Index of Last Occurrence)
* implementations</p>
* @param arr integer array
* @param x element to find count for
* @return total count for given element
*/
public static int of(int[] arr, int x) {
int first = FirstOccurrence.of(arr, x);
if (first == -1) return 0;
else return LastOccurrence.of(arr, x) - first + 1;
}
}
