Find Frequency In Sorted Array

Problem Statement

This is a question from one of the interview experiences. You are given a sorted array of numbers (this can be extended for arrays of characters, strings and what not) and a number K. Find the number of occurrences of K in the array.

Solution

Yes you got that right, it is really very simple. Walk through the array sequentially and if you get K then start counting till you get anything bigger than K. You can break out of the loop after this and the counter will tell you the obvious answer.

So, why am I even writing this post?

Because this is not fun, the above approach tells us the answer in asymptotically linear time. That means the solution has a running time complexity O(N) where the number of elements in the array is N. You might get lucky where the array has the Ks in the beginning, but that is just luck. Mostly the solution is O(N) and it will remain same.

So, let us put some fun in it.

I want the solution is lesser time. How better can we solve this for? Do you really think we need to look at each element even if the element K lies in the end off the array?

The key is to find the first and the last index of K in the array. I am sure you would have guessed till now. The answer is Binary Search. Moreover, it would be modifying the Binary Search Algorithm to return the first and last index of K in the array. Adding one to the difference of these two numbers would give us the frequency.
Find Frequency In Sorted Array
In the above array the first index of three is 2 and the last index of three is 3. Hence the frequency is 3 – 2 + 1 = 2.
Similarly the first index of five is 7 and the last index of five is 9. The frequency is 9 – 7 + 1 = 3.

Pseudo Code – First or Last Index in Array

We just invoke the above routine twice, once with firstIndex = true and then with firstIndex = false and get the difference.

Source Code – Find Frequency In Sorted Array

Analysis

We really do not need any analysis, its plain binary search and running time is asymptotically O(logN), of course the constant terms may have a higher value. But its still O(logN).
Auxiliary space – None, except for few counters, so its constant O(1).

Don’t forget to subscribe to TechieMe to get updates on latest posts.