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

C++

Download   Run Code

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

Download   Run Code

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.

C++

Download   Run Code

Java

Download   Run Code

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.

 

Download   Run Code

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

 
Thanks for reading.

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 🙂 


 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Rnet
Guest
Rnet

This can also be done using binary range search. You can modify binary search to find the lower/higher end.

Start with first element, do a bin search to find it’s upper end, count the len difference, then select the upper end + 1 element and repeat the same.

Time Complexity = m (logn)