Lv.1arraybinary-search
Count in Range of a Sorted Array
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
You are given an integer array nums sorted in non-decreasing order and an array queries. For each queries[i] = [lo, hi],
count the elements of nums with lo ≤ x ≤ hi (duplicates count separately) and return the counts in query order.
Examples
| nums | queries | result |
|---|---|---|
[1, 3, 3, 5, 8, 13] | [[3, 5], [4, 7], [0, 100], [9, 12]] | [3, 1, 6, 0] |
[-2, 0, 0, 0, 7] | [[0, 0], [-5, -1]] | [3, 1] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(nums: int[], queries: int[][]) → int[]
Constraints
-
nums.length, sorted non-decreasing;nums[i] -
queries.length,queries[i] = [lo, hi]with
Expected complexity
- Time
- O((N + Q) log N)
- Space
- O(1)
Examples
| nums | queries | Expected |
|---|---|---|
[1,3,3,5,8,13] | [[3,5],[4,7],[0,100],[9,12]] | [3,1,6,0] |
[-2,0,0,0,7] | [[0,0],[-5,-1]] | [3,1] |
Hint
Hint
The answer is upper_bound(hi) - lower_bound(lo), two binary searches per query. Scanning the array for every query is
and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 452 ms | estimated |
| C++ (GCC, gnu++23) | 452 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 2196 ms | derived |
| Kotlin 2.4 (JVM) | 1904 ms | estimated |
| C# 14 (.NET 10) | 1904 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 8 | verdict only |
| performance | 60 | 4 | verdict only |