DSA interview question

Count Occurrences in a Sorted Array

Easy · Algorithms · Topics: binary search, array

The problem

A survey platform stores every response's rating in a sorted array, and the results page shows how many people chose each rating. With millions of responses and only the sorted array available, the count for one rating comes from its first and last positions: last − first + 1. That's two O(log n) binary searches, instead of scanning a block that might contain millions of equal values.

Example: [1, 1, 2, 2, 2, 2, 3], x = 2 → 4.

Function signature

int countOccurrences(const vector<int>& a, int x);  // number of times x appears in sorted a

Test cases

Input `(a, x)`	Output	Explanation
`([1, 1, 2, 2, 2, 2, 3], 2)`	4	Indices 2 to 5
`([1, 1, 2, 2, 2, 2, 3], 4)`	0	Not present
`([1, 1, 2, 2, 2, 2, 3], 1)`	2	At the start
`([5], 5)`	1
`([], 3)`	0

(Confirm: the array is sorted non-decreasingly; O(log n) is expected.)

How interviewers phrase it

"Count the occurrences of X in a sorted array" (GeeksforGeeks "Number of occurrence").
"How many elements equal X, in O(log n)?"

Clarifying questions to ask

Is the array sorted?
Is O(log n) required, or is a linear scan acceptable?

Follow-ups to expect

"How do you get the count?"
"Another way?"
"How do you count elements in a range [L, R]?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview