Sparse Table (Static Range Minimum)
Advanced
nums never changes. Each query [l, r] asks for the smallest value in nums[l..r] (both ends included). Return the answers in order.
For nums = [5, 2, 8, 1, 9] and queries = [[0, 4], [1, 2], [2, 2]] the answer is [1, 2, 8].
The starter code scans the range for each query. It is correct but too slow for many queries.
Examples
Example 1
Input:
range_minimums([5, 2, 8, 1, 9], [[0, 4], [1, 2], [2, 2]])
Output:
[1, 2, 8]
Example 2
Input:
range_minimums([3], [[0, 0]])
Output:
[3]
Constraints
1 <= len(nums) <= 655360 <= len(queries) <= 1000000 <= l <= r < len(nums)-10**9 <= nums[i] <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetdesignrange-structures
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.