Skip to content
Onsite
7 / 20

Frequency in Sorted Array

MediumP1Coding

nums is sorted in non-decreasing order and may contain duplicates. For each value in queries, count how many times it appears in nums. Return the counts in query order.

Each query must take O(log n), so do not scan the array per query.

Example 1

Input
nums = [1,2,2,2,3,5], queries = [2,4,1,5]
Output
[3,0,1,1]

Example 2

Input
nums = [7], queries = [7,8]
Output
[1,0]

Example 3

Input
nums = [1,1,1,1], queries = [1]
Output
[4]

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= queries.length <= 10^5
  • -10^9 <= nums[i], queries[j] <= 10^9
  • nums is sorted in non-decreasing order.

Hints

Run checks the 3 visible tests, Submit all 8.