Log inSign up
easyGeeksforGeeksNot Started

Count Occurrences in Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array arr of N positive integers and a number x, find the number of occurrences of x in arr.

If x does not appear in arr, return 0.

You must write an algorithm with O(log n) runtime complexity.

Example 1 · Element Appears Multiple Times:

Input: arr = [1, 1, 2, 2, 2, 2, 3], x = 2
Output: 4
Explanation: 2 appears 4 times (indices 2, 3, 4, 5).

Example 2 · Element Appears Once:

Input: arr = [1, 1, 2, 2, 2, 2, 3], x = 3
Output: 1
Explanation: 3 appears only once at index 6.

Example 3 · Element Absent from Array:

Input: arr = [1, 1, 2, 2, 2, 2, 3], x = 4
Output: 0
Explanation: 4 is not in arr so return 0.

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i], x <= 106
  • arr is sorted in non-decreasing (ascending) order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine two independent binary search procedures to find contiguous sub-ranges.
  • Understand why last - first + 1 is strictly O(log N) compared to O(N) linear scanning.
  • Formulate STL one-liners using std::equal_range or upper_bound - lower_bound.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Count frequency of an element in a sorted array
  • Requirement for O(log N) runtime instead of O(N) frequency counting
  • Contiguous duplicates property

Algorithmic Decision Tree:

  • Compute first = getFirstOccurrence(arr, x).
  • If first == -1, return 0.
  • Compute last = getLastOccurrence(arr, x).
  • Return last - first + 1.

Connected Patterns:

First Occurrence of an ElementLast Occurrence of an ElementUpper BoundLower Bound

1. Linear Frequency Counting

Intuition

Loop through all elements from index 0 to n - 1. If arr[i] == x, increment count. Return count at the end.

When to apply: Unsorted collections.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: Iterate through all elements in arr.
  3. Step 3: If arr[i] == x, increment count by 1.
  4. Step 4: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int countOccurrences(const vector<int>& arr, int x) {
7 int count = 0;
8 for (int num : arr) {
9 if (num == x) count++;
10 }
11 return count;
12}
13
14int main() {
15 vector<int> arr = {1, 1, 2, 2, 2, 2, 3};
16 cout << "Linear count of 2: " << countOccurrences(arr, 2) << endl;
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(N) — Scans all N elements linearly.
  • Space complexity: O(1) — Uses a single integer counter.

2. STL Bounds Difference (upper_bound - lower_bound)

Intuition

Using standard library binary search primitives: lower_bound finds the first index where arr[i] >= x, and upper_bound finds the first index where arr[i] > x. The difference upper_bound(x) - lower_bound(x) equals the frequency of x.

When to apply: Clean C++ STL / Python bisect implementations.

Algorithm

  1. Step 1: Compute lb = lower_bound(arr, x).
  2. Step 2: Compute ub = upper_bound(arr, x).
  3. Step 3: Return ub - lb.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int countOccurrences(const vector<int>& arr, int x) {
8 auto lb = lower_bound(arr.begin(), arr.end(), x);
9 auto ub = upper_bound(arr.begin(), arr.end(), x);
10 return distance(lb, ub);
11}
12
13int main() {
14 vector<int> arr = {1, 1, 2, 2, 2, 2, 3};
15 cout << "STL Bounds count of 2: " << countOccurrences(arr, 2) << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(log N) — Two binary searches each take O(log N) time.
  • Space complexity: O(1) — Constant auxiliary memory.

3. Dual Binary Search (First & Last Occurrence) (Gold Standard)

Intuition

Run getFirstOccurrence(arr, x): if first == -1, target is absent, return 0 early without running second search. Run getLastOccurrence(arr, x): return last - first + 1.

When to apply: Industry standard optimal solution for frequency of element in sorted collections.

Algorithm

  1. Step 1: Execute binary search to find first occurrence index first.
  2. Step 2: If first == -1, target does not exist in array; return 0 immediately.
  3. Step 3: Execute binary search to find last occurrence index last.
  4. Step 4: Return last - first + 1.

Count Occurrences Range Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Run First Occurrence Binary Search for x = 2
Visual state
Values and pointers at this exact step
array
S
1
1
2
2
2
2
3
0
1
2
↑ first
3
4
5
6
Variables at this step
first
2
last
null
target
2
Check / comparison
First occurrence located at index 2
Decision / next transition
first = 2. Since first != -1, proceed to find last occurrence.
Why this step matters

Run First Occurrence Binary Search for x = 2. Leftmost match found at index 2 (first = 2).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int getFirst(const vector<int>& arr, int x) {
8 int low = 0, high = (int)arr.size() - 1, ans = -1;
9 while (low <= high) {
10 int mid = low + (high - low) / 2;
11 if (arr[mid] == x) { ans = mid; high = mid - 1; }
12 else if (arr[mid] < x) low = mid + 1;
13 else high = mid - 1;
14 }
15 return ans;
16 }
17
18 int getLast(const vector<int>& arr, int x) {
19 int low = 0, high = (int)arr.size() - 1, ans = -1;
20 while (low <= high) {
21 int mid = low + (high - low) / 2;
22 if (arr[mid] == x) { ans = mid; low = mid + 1; }
23 else if (arr[mid] < x) low = mid + 1;
24 else high = mid - 1;
25 }
26 return ans;
27 }
28
29public:
30 int count(vector<int>& arr, int x) {
31 int first = getFirst(arr, x);
32 if (first == -1) return 0;
33 int last = getLast(arr, x);
34 return last - first + 1;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> arr = {1, 1, 2, 2, 2, 2, 3};
41 int x = 2;
42 cout << "Count of " << x << " is: " << sol.count(arr, x) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(log N) — Two binary search runs take 2 * log2(N) = O(log N) operations with early exit.
  • Space complexity: O(1) — Zero auxiliary memory allocated.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear ScanO(N)O(1)Count elements sequentially.Linear scan
2.STL upper_bound - lower_boundO(log N)O(1)Use library functions to find difference.None
3.Dual Binary Search (First & Last)OptimalO(log N)O(1)Find first and last indices with early return if absent.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Running a linear while-loop after finding one occurrence (degrades to O(N) when array contains 105 duplicates).

Pitfall 2:

Forgetting the + 1 in (last - first + 1).

Crucial Edge Cases to Validate:

  • Element Absent: arr = [1, 2, 4, 5], x = 3 -> first = -1 -> returns 0.
  • All Elements Equal: arr = [5, 5, 5, 5, 5], x = 5 -> first = 0, last = 4 -> returns 5.
  • Single Element Array [3], x = 3 -> returns 1; x = 2 -> returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Warn the interviewer why expanding linearly outwards from a single found mid degrades to O(N) worst-case time, proving why dual binary search is required.
  2. Mention std::equal_range in C++ as the standard library equivalent.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is early exit when first == -1 an optimization in Dual Binary Search?

2.What is the time complexity of finding occurrences of x in a sorted array of size N = 106?

Back to DSA Sheet