Find Frequency of each element in a sorted array containing duplicates

Given a sorted array containing duplicates, efficiently find frequency of each element in it without traversing the whole array.

For example,

Input: [2, 2, 2, 4, 4, 4, 5, 5, 6, 8, 8, 9]

Output:

2 occurs 3 times
4 occurs 3 times
5 occurs 2 times
6 occurs 1 times
8 occurs 2 times
9 occurs 1 times

A simple solution would be to run a linear search on the array and count number of occurrence of each element and finally print them. The problem with this approach is that its worst case time complexity is O(n) and we’re scanning the whole array (violating problem constraints).

1. Recursive implementation –

We can easily solve this problem in O(mlogn) time with recursion by taking advantage of the fact that the input is sorted and there are duplicates present. Here m is the number of distinct elements in the array and n is the size of the input. The idea is to simply split the array to two equal halves and recurse for both the halves. The base condition checks if the last element of the sub-array is same as its first element. If they are equal, then that implies that all elements in the sub-array are similar (since array is sorted) and we update the element count by number of elements in the sub-array (in constant time).

Output:

9 occurs 1 times
8 occurs 2 times
2 occurs 3 times
4 occurs 3 times
5 occurs 2 times
6 occurs 1 times

Java

Output:

{2=3, 4=3, 5=2, 6=1, 8=2, 9=1}

2. Iterative implementation –

Below is the iterative implementation of it. The implementation basically updates the frequency of each distinct element of the array one at a time and grow/shrink the array dynamically to consider each element.

Java

Output:

2 occurs 3 times
4 occurs 3 times
5 occurs 2 times
6 occurs 1 times
8 occurs 2 times
9 occurs 1 times

3. STL implementation –

We can easily solve this problem using STL as well. The idea is to find the index of first and last occurrence of every distinct number in the array and update the difference between two indices in a map. In solution below, we will use STL’s std::upper_bound and std::lower_bound to find first/last occurrence using binary search.

Output:

9 occurs 1 times
8 occurs 2 times
2 occurs 3 times
4 occurs 3 times
5 occurs 2 times
6 occurs 1 times

Time complexity of all above solutions is O(mlogn) where m is the number of distinct elements in the array and n is the size of the input. Auxiliary space used by the program is O(1).

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂