Sparse Table Range Minimum

Problem

Answer static range-minimum queries with a sparse table.

nums is fixed. queries is a list of [l, r] pairs and each answer is min(nums[l..r]). Precompute the minima of all intervals whose length is a power of two so each query needs only two overlapping blocks.

Return the list of answers.

Hint

The minimum of a range is the minimum of the two power-of-two blocks covering it.

Test cases

case 1

in: [[4,2,7,1,3],[[1,3],[0,4],[2,2]]]

expected: [1,1,7]

case 2

in: [[5],[[0,0]]]

expected: [5]

case 3

in: [[3,1,4,1,5,9,2,6],[[0,3],[4,7],[2,5]]]

expected: [1,2,1]

case 4

in: [[],[]]

expected: []

Starter codePython

def sparse_table_min(nums, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor