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

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

1 2 3 4 5 6 7 8 9 |
firstOrLastIndex(A[], k, high, low, firstIndex) position = -1 mid = low + (high - low) / 2 while low <= high if A[mid] == k position = k if firstIndex high = mid - 1 else low = mid + 1 else if A[mid] > k low = mid + 1 else high = mid - 1 return position |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class FindFrequency { public static void main(String[] args) { int[] A = new int[] { 1 ,2, 4, 4, 4, 4, 4, 7, 8, 9 }; FindFrequency driver = new FindFrequency(); int firstIndex = driver.firstOrLastIndex(A, 4, 0, A.length - 1, true); int lastIndex = -1; int K = 4; if (firstIndex != -1) { lastIndex = driver.firstOrLastIndex(A, K, firstIndex, A.length - 1, false); } System.out.println(lastIndex - firstIndex + 1); } private int firstOrLastIndex(int[] A, int K, int low, int high, boolean firstIndex) { int position = -1; int mid = -1; while (low <= high) { mid = low + (high - low) / 2; if (A[mid] == K) { position = mid; if (firstIndex) high = mid - 1; else low = mid + 1; } else if (A[mid] > K) high = mid - 1; else low = mid + 1; } return position; } } |

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