996. Distinct in Range
A warehouse shelf has n slots in a line, and slot i holds an item of kind nums[i] (kinds are integers; two slots with the same number hold the same kind). An inspector sends questions queries[j] = [l, r], meaning: look only at slots l through r (0-indexed, both included).
For every question, report how many different kinds of item appear in that window. Return an array result where result[j] answers queries[j]. Windows may overlap and repeat. Counting each kind once per window, however many slots it occupies, is the whole point.
Example 1
- Input:
- nums = [4,7,4,9,7,7]queries = [[0,5],[1,2],[2,4],[5,5]]
- Output:
- [3,2,3,1]
- Explanation:
Positions 0..5 hold the distinct values 4, 7, 9 (3); positions 1..2 hold 7 and 4 (2); positions 2..4 hold 4, 9, 7 (3); a single position has 1 distinct value.
Example 2
- Input:
- nums = [3,3,3,3], queries = [[0,3],[1,2]]
- Output:
- [1,1]
- Explanation:
Every shelf slot has the same item, so any window shows exactly one kind.
Example 3
- Input:
- nums = [5,-1,5,-1,8], queries = [[0,1],[0,4],[3,4]]
- Output:
- [2,3,2]
- Explanation:
Slots 0..1 show 5 and -1; slots 0..4 show 5, -1, 8; slots 3..4 show -1 and 8.
Constraints
- 1 ≤ nums.length ≤ 105
- 1 ≤ queries.length ≤ 105
- -109 ≤ nums[i] ≤ 109
- 0 ≤ l ≤ r < nums.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n + q)