Count Occurrences in Sorted Array | Dataford Interview Questions

Blinkit's catalog and fulfillment systems may store sorted item IDs with repeated values. Given a sorted array and a target item ID, return how many times the target occurs.

Your solution must use binary search rather than scanning every element. Find the first index where the target could appear and the first index after its final occurrence. Their difference is the required count.

Formal Specification

Implement count_occurrences(nums, target).

Input: nums, a list of integers sorted in non-decreasing order, and target, an integer.
Output: An integer representing the number of elements in nums equal to target.
Return 0 when the target is absent.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i], target <= 10^9
nums is sorted in non-decreasing order
The required algorithm runs in O(log n) time

Function Signature

def count_occurrences(nums, target):

Your question is Count Occurrences in Sorted Array. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem