Count Occurrences of Element in Sorted Array in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of counting occurrences using binary search

What is the output of the following code that counts occurrences of 3 in a sorted array?

DSA Javascript

function countOccurrences(arr, x) {
  function firstOccurrence() {
    let low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        result = mid;
        high = mid - 1;
      } else if (arr[mid] < x) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return result;
  }

  function lastOccurrence() {
    let low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        result = mid;
        low = mid + 1;
      } else if (arr[mid] < x) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return result;
  }

  let first = firstOccurrence();
  if (first === -1) return 0;
  let last = lastOccurrence();
  return last - first + 1;
}

console.log(countOccurrences([1,2,3,3,3,4,5], 3));

A 3

B 2

C 1

D 0

💡 Hint

Think about how binary search finds the first and last positions of the target.

The code finds the first and last index of the element 3 in the sorted array. The element 3 appears at indices 2, 3, and 4, so the count is 3.

❓ Predict Output

intermediate

Output when element is not present

What is the output of the code when counting occurrences of 6 in the sorted array?

DSA Javascript

function countOccurrences(arr, x) {
  function firstOccurrence() {
    let low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        result = mid;
        high = mid - 1;
      } else if (arr[mid] < x) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return result;
  }

  function lastOccurrence() {
    let low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        result = mid;
        low = mid + 1;
      } else if (arr[mid] < x) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return result;
  }

  let first = firstOccurrence();
  if (first === -1) return 0;
  let last = lastOccurrence();
  return last - first + 1;
}

console.log(countOccurrences([1,2,3,3,3,4,5], 6));

A 1

B undefined

C 5

D 0

💡 Hint

If the element is not found, the function returns 0.

Since 6 is not in the array, the firstOccurrence function returns -1, so the countOccurrences function returns 0.

🔧 Debug

advanced

Identify the error in counting occurrences code

What error does the following code produce when counting occurrences of 3 in the array?

DSA Javascript

function countOccurrences(arr, x) {
  function firstOccurrence() {
    let low = 0, high = arr.length - 1, result = -1
    while (low <= high) {
      let mid = Math.floor((low + high) / 2)
      if (arr[mid] === x) {
        result = mid
        high = mid - 1
      } else if (arr[mid] < x) {
        low = mid + 1
      } else {
        high = mid - 1
      }
    }
    return result
  }

  function lastOccurrence() {
    let low = 0, high = arr.length - 1, result = -1
    while (low <= high) {
      let mid = Math.floor((low + high) / 2)
      if (arr[mid] === x) {
        result = mid
        low = mid + 1
      } else if (arr[mid] < x) {
        low = mid + 1
      } else {
        high = mid - 1
      }
    }
    return result
  }

  let first = firstOccurrence()
  if (first === -1) return 0
  let last = lastOccurrence()
  return last - first + 1
}

console.log(countOccurrences([1,2,3,3,3,4,5], 3))

A The code runs and returns 3

B Infinite loop due to incorrect update of high and low pointers

C SyntaxError due to missing semicolons

D TypeError because result is undefined

💡 Hint

Check how the pointers low and high are updated inside the loops.

The code incorrectly updates high = mid - 1 and low = mid + 1 in the correct version, but in this buggy code, it uses high = mid + 1 and low = mid - 1, which can cause the loop to never terminate, resulting in an infinite loop.

❓ Predict Output

advanced

Output of counting occurrences with duplicates at edges

What is the output of counting occurrences of 2 in the array with duplicates at the edges?

DSA Javascript

function countOccurrences(arr, x) {
  function firstOccurrence() {
    let low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        result = mid;
        high = mid - 1;
      } else if (arr[mid] < x) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return result;
  }

  function lastOccurrence() {
    let low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        result = mid;
        low = mid + 1;
      } else if (arr[mid] < x) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return result;
  }

  let first = firstOccurrence();
  if (first === -1) return 0;
  let last = lastOccurrence();
  return last - first + 1;
}

console.log(countOccurrences([2,2,2,3,4,5,6], 2));

A 1

B 2

C 3

D 0

💡 Hint

Duplicates at the start should be counted correctly.

The element 2 appears three times at the start of the array, so the count is 3.

🚀 Application

expert

Count occurrences in a large sorted array efficiently

You have a sorted array of 1 million integers with many duplicates. Which approach is the most efficient to count occurrences of a given element x?

A Use binary search to find the first and last occurrence of x, then calculate the count

B Use a hash map to store counts of all elements, then retrieve count of x

C Sort the array first, then count occurrences using a hash map

D Use a linear scan to count all occurrences of x in the array

💡 Hint

Think about the time complexity of searching in a sorted array.

Binary search finds the first and last occurrence in O(log n) time, which is much faster than scanning or building hash maps for large arrays.

Practice

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

easy

A. It sorts the array automatically.

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

C. It counts all elements without searching.

D. It works only on unsorted arrays.

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 linear vs binary search

   Linear search checks each element one by one (O(n)), binary search works in O(log n) time.

3. Final Answer:

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

4. Quick Check:

   Binary search = faster search [OK]

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

Common Mistakes:

• Thinking binary search sorts the array
• Assuming binary search works on unsorted arrays
• Confusing counting with searching

2. Which of the following is the correct syntax to find the middle index in a binary search on array arr between indices low and high in JavaScript?

easy

A. const mid = low + high;

B. const mid = (low + high) / 2;

C. const mid = Math.ceil((low + high) / 2);

D. const mid = Math.floor((low + high) / 2);

Solution

1. Step 1: Calculate middle index correctly

   We use Math.floor to get the integer index because array indices must be whole numbers.

2. Step 2: Avoid floating point and wrong calculations

   Using just division or Math.ceil can cause errors or out-of-bound indices.

3. Final Answer:

   const mid = Math.floor((low + high) / 2); -> Option D

4. Quick Check:

   Use Math.floor for middle index [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Not using Math.floor causing float index
• Using Math.ceil which may skip elements
• Adding indices without division

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

function countOccurrences(arr, x) {
  let low = 0, high = arr.length - 1;
  let count = 0;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === x) {
      count++;
      let left = mid - 1;
      while (left >= 0 && arr[left] === x) {
        count++;
        left--;
      }
      let right = mid + 1;
      while (right < arr.length && arr[right] === x) {
        count++;
        right++;
      }
      break;
    } else if (arr[mid] < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return count;
}

console.log(countOccurrences([1,2,2,2,3,4,5], 2));

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Find one occurrence of 2 using binary search

   The binary search finds 2 at index 2 (middle of array).

2. Step 2: Count all adjacent 2s on left and right

   Left side: indices 1 and 0 checked; only index 1 has 2. Right side: index 3 has 2. Total count = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Count adjacent 2s = 3 [OK]

Hint: Count neighbors after binary search hit [OK]

Common Mistakes:

• Counting only the found element once
• Not checking neighbors on both sides
• Incorrect loop conditions causing infinite loops

4. The following code is intended to count occurrences of x in a sorted array arr. What is the bug?

function countOccurrences(arr, x) {
  let low = 0, high = arr.length - 1;
  let count = 0;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === x) {
      count++;
      let left = mid - 1;
      while (arr[left] === x) {
        count++;
        left--;
      }
      let right = mid + 1;
      while (arr[right] === x) {
        count++;
        right++;
      }
      break;
    } else if (arr[mid] < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return count;
}

medium

A. The while loops do not check array bounds before accessing elements.

B. The binary search condition is incorrect.

C. The count variable is not initialized.

D. The function does not return any value.

Solution

1. Step 1: Analyze while loops for boundary checks

   The loops check arr[left] === x and arr[right] === x without verifying if left or right are valid indices.

2. Step 2: Identify risk of out-of-bounds access

   If left becomes -1 or right exceeds array length, accessing arr[left] or arr[right] causes errors.

3. Final Answer:

   The while loops do not check array bounds before accessing elements. -> Option A

4. Quick Check:

   Always check array bounds before access [OK]

Hint: Check array bounds before accessing elements [OK]

Common Mistakes:

• Ignoring array index limits in loops
• Assuming array access is always safe
• Not breaking loop on invalid index

5. Given a sorted array arr = [1,2,2,2,3,3,4,5,5,5,5,6], which approach is the most efficient to count occurrences of 5 without scanning the entire array?

hard

A. Use binary search to find first and last positions of 5, then calculate count.

B. Use a for loop to count all 5s by scanning the whole array.

C. Sort the array again and count 5s.

D. Use a hash map to store counts of all elements.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, so all 5s are grouped together.

2. Step 2: Use binary search to find boundaries

   Find the first index of 5 and last index of 5 using binary search, then count = last - first + 1.

3. Step 3: Compare efficiency

   This method is O(log n), faster than scanning entire array (O(n)) or sorting again (O(n log n)).

4. Final Answer:

   Use binary search to find first and last positions of 5, then calculate count. -> Option A

5. Quick Check:

   Binary search boundaries = efficient count [OK]

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

Common Mistakes:

• Scanning entire array unnecessarily
• Sorting already sorted array again
• Using extra space with hash map when not needed