Count Occurrences of Element in Sorted Array in DSA Typescript

Mental Model

Find where the element starts and ends in the sorted list, then count how many times it appears.

Analogy: Imagine a row of identical books on a shelf sorted by title. To count how many copies of one title are there, find the first copy and the last copy, then count all in between.

Array: [1, 2, 2, 2, 3, 4, 5]
Find element: 2
Positions: start ↑ at first 2, end ↑ at last 2

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4, 5], element to count: 2

Goal: Count how many times 2 appears in the sorted array

Step 1: Find first occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
First occurrence index found at 1

Why: We need the first position where 2 appears to start counting

Step 2: Find last occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
Last occurrence index found at 3

Why: We need the last position where 2 appears to end counting

Step 3: Calculate count as last index - first index + 1

Count = 3 - 1 + 1 = 3

Why: Counting all elements from first to last occurrence gives total appearances

Result:

Array: [1, 2, 2, 2, 3, 4, 5]
Element 2 occurs 3 times

Annotated Code

DSA Typescript

class SortedArray {
  arr: number[];

  constructor(arr: number[]) {
    this.arr = arr;
  }

  // Find first occurrence index of target
  firstOccurrence(target: number): number {
    let low = 0;
    let high = this.arr.length - 1;
    let result = -1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.arr[mid] === target) {
        result = mid; // record current match
        high = mid - 1; // search left side for earlier occurrence
      } else if (this.arr[mid] < target) {
        low = mid + 1; // move right
      } else {
        high = mid - 1; // move left
      }
    }
    return result;
  }

  // Find last occurrence index of target
  lastOccurrence(target: number): number {
    let low = 0;
    let high = this.arr.length - 1;
    let result = -1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.arr[mid] === target) {
        result = mid; // record current match
        low = mid + 1; // search right side for later occurrence
      } else if (this.arr[mid] < target) {
        low = mid + 1; // move right
      } else {
        high = mid - 1; // move left
      }
    }
    return result;
  }

  // Count occurrences of target
  countOccurrences(target: number): number {
    const first = this.firstOccurrence(target);
    if (first === -1) return 0; // target not found
    const last = this.lastOccurrence(target);
    return last - first + 1;
  }
}

// Driver code
const arr = [1, 2, 2, 2, 3, 4, 5];
const target = 2;
const sortedArray = new SortedArray(arr);
const count = sortedArray.countOccurrences(target);
console.log(`Array: [${arr.join(", ")}]`);
console.log(`Element ${target} occurs ${count} times`);

if (this.arr[mid] === target) { result = mid; high = mid - 1; }

record first occurrence and continue searching left to find earlier index

if (this.arr[mid] === target) { result = mid; low = mid + 1; }

record last occurrence and continue searching right to find later index

if (first === -1) return 0;

handle case when target is not found in array

return last - first + 1;

calculate total count from first to last occurrence indices

Output

Array: [1, 2, 2, 2, 3, 4, 5]

Element 2 occurs 3 times

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach scans entire array O(n), this method is faster for large sorted arrays

Edge Cases

Element not present in array

Returns count 0 because first occurrence returns -1

DSA Typescript

if (first === -1) return 0;

Array with one element equal to target

Returns count 1 correctly

DSA Typescript

return last - first + 1;

Array with all elements equal to target

Returns count equal to array length

DSA Typescript

return last - first + 1;

When to Use This Pattern

When you need to count how many times a number appears in a sorted list, use binary search to find first and last positions for efficient counting.

Common Mistakes

Mistake: Using linear scan instead of binary search, causing slow performance
Fix: Use binary search to find first and last occurrences to achieve O(log n) time

Mistake: Not updating search boundaries correctly when target is found
Fix: Adjust high or low pointers to continue searching left or right for first or last occurrence

Mistake: Not handling case when target is not found, returning wrong count
Fix: Check if first occurrence is -1 and return 0 immediately

Summary

Counts how many times a given element appears in a sorted array efficiently.

Use when you have a sorted list and want to quickly find the frequency of an element.

Find the first and last positions of the element using binary search, then count the elements between.