Count Occurrences in Sorted Array

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Count Occurrences in Sorted Array. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output