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.