progress

~/problems / Arrays & hashing / Python toolkit

Count scores in a range with bisect

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

A teacher keeps every test score in a list (in no particular order) and keeps asking questions like "how many scores are between 80 and 90?".

Write count_in_range(scores: list[int], queries: list[tuple[int, int]]) -> list[int]. For each query (lo, hi), count the scores s with lo <= s <= hi (both ends inclusive). Return the counts in query order.

count_in_range([70, 85, 90, 85, 60, 100], [(80, 90), (0, 59), (85, 85), (95, 200)])
# [3, 0, 2, 1]

(80 to 90 holds 85, 85 and 90; 85 to 85 holds the two 85s.)

  • 0 <= len(scores) <= 10^5 and 0 <= len(queries) <= 10^5. Values are in [-10^9, 10^9], scores may repeat, and every query has lo <= hi.
  • Don't modify scores.

⭐ Bonus: scanning every score for every query is O(n·q) and still passes; a speed test with 100,000 scores and 100,000 queries earns a star if you sort once and answer each query in O(log n).

Show hint

on a sorted list, bisect.bisect_left(a, lo) is how many values are below lo, and bisect.bisect_right(a, hi) is how many are at most hi.

Topic: Python toolkit. Counter, deque, heapq, bisect, itertools: the standard library to know cold, and its traps.

0:00
Ctrl ' run · Ctrl ↵ submit
esc