Funcia
Lv.1arraybinary-search

Count in Range of a Sorted Array

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

numsqueriesresult
[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

  • 1≤1 \le nums.length ≤200,000\le 200{,}000, sorted non-decreasing; −109≤-10^9 \le nums[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000, queries[i] = [lo, hi] with −109≤lo≤hi≤109-10^9 \le lo \le hi \le 10^9

Expected complexity

Time
O((N + Q) log N)
Space
O(1)

Examples

numsqueriesExpected
[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 O(NQ)O(NQ) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)452 msestimated
C++ (GCC, gnu++23)452 msderived
Python 3.131000 msderived
Java 252196 msderived
Kotlin 2.4 (JVM)1904 msestimated
C# 14 (.NET 10)1904 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.