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.

Practice

1. What is the main advantage of using a binary search approach to count occurrences of an element in a sorted array?

easy

A. It allows counting occurrences without sorting the array.

B. It works only for unsorted arrays.

C. It uses less memory than a linear search.

D. It reduces the search time from linear to logarithmic.

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, making it faster than checking every element.

2. Step 2: Compare with linear search

   Linear search checks each element one by one, which takes more time for large arrays.

3. Final Answer:

   It reduces the search time from linear to logarithmic. -> Option D

4. Quick Check:

   Binary search = faster search [OK]

Hint: Binary search halves search space each step [OK]

Common Mistakes:

• Thinking binary search works on unsorted arrays
• Confusing memory use with speed
• Assuming linear search is faster

2. Which of the following TypeScript function signatures correctly represents a function to count occurrences of a number in a sorted array?

easy

A. function countOccurrences(arr: number[], target: number): number

B. function countOccurrences(arr: number, target: number[]): number

C. function countOccurrences(arr: string[], target: string): string

D. function countOccurrences(arr: number[], target: number): void

Solution

1. Step 1: Check parameter types

   The array should be of numbers and the target should be a number to count occurrences.

2. Step 2: Check return type

   The function should return a number representing the count, not void or string.

3. Final Answer:

   function countOccurrences(arr: number[], target: number): number -> Option A

4. Quick Check:

   Correct types and return number [OK]

Hint: Array and target types must match; return count as number [OK]

Common Mistakes:

• Swapping array and target types
• Returning void instead of number
• Using string types for numbers

3. What will be the output of the following TypeScript code?

function countOccurrences(arr: number[], target: number): number {
  const first = arr.indexOf(target);
  if (first === -1) return 0;
  let count = 0;
  for (let i = first; i < arr.length && arr[i] === target; i++) {
    count++;
  }
  return count;
}

const nums = [1, 2, 2, 2, 3, 4];
console.log(countOccurrences(nums, 2));

medium

A. 3

B. 2

C. 0

D. 4

Solution

1. Step 1: Find first occurrence index

   arr.indexOf(2) returns 1, the first position of 2 in the array.

2. Step 2: Count consecutive occurrences

   From index 1, elements are 2, 2, 2 (3 times), so count is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Start counting from first index of target [OK]

Common Mistakes:

• Counting all 2s without checking consecutive
• Returning index instead of count
• Ignoring if target not found

4. The following TypeScript function is intended to count occurrences of target in a sorted array arr. What is the bug?

function countOccurrences(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      let count = 1;
      let i = mid + 1;
      while (i < arr.length && arr[i] === target) {
        count++;
        i++;
      }
      return count;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return 0;
}

medium

A. The function counts occurrences incorrectly by missing some elements.

B. The binary search loop condition should be < instead of <=.

C. The function does not find the first occurrence before counting.

D. The function does not handle empty arrays.

Solution

1. Step 1: Analyze binary search usage

   The function finds any occurrence of target but not necessarily the first one.

2. Step 2: Understand counting logic

   The function counts from the found mid only to the right. If mid is not the first occurrence, it misses the elements to the left.

3. Final Answer:

   The function does not find the first occurrence before counting. -> Option C

4. Quick Check:

   First occurrence needed for accurate count [OK]

Hint: Find first occurrence before counting neighbors [OK]

Common Mistakes:

• Counting from any found index without adjusting
• Changing loop condition incorrectly
• Ignoring empty array edge case

5. Given a sorted array arr and a target number t, which approach correctly counts the occurrences of t in arr in O(log n) time?

Choose the best method.

hard

A. Use binary search to find any occurrence of t and return 1 immediately.

B. Use binary search to find the first and last occurrence of t, then calculate count as last - first + 1.

C. Sort the array again and then count occurrences using indexOf and lastIndexOf.

D. Use a linear loop to count all elements equal to t from start to end.

Solution

1. Step 1: Understand time complexity requirements

   Counting occurrences in O(log n) requires binary search, not linear scanning.

2. Step 2: Use binary search twice

   Find first occurrence index and last occurrence index of target using binary search, then count is last - first + 1.

3. Final Answer:

   Use binary search to find the first and last occurrence of t, then calculate count as last - first + 1. -> Option B

4. Quick Check:

   Binary search twice = O(log n) count [OK]

Hint: Find first and last index with binary search [OK]

Common Mistakes:

• Using linear search for counting in sorted array
• Sorting array again unnecessarily
• Returning 1 after finding any occurrence