Range Minimum Query Sparse Table

Problem

Answer inclusive range minimum queries on a static list of integers, returning the answers in query order.

Precompute a sparse table where entry k covers intervals of length 2 to the k, then answer each query by combining the two overlapping power-of-two intervals. An empty list returns an empty result.

Hint

Two overlapping blocks of length 2 to the floor of log length cover any range.

Test cases

case 1

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

expected: [1,1,3]

case 2

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

expected: [5]

case 3

in: [[],[]]

expected: []

case 4

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

expected: [3,3]

case 5

in: [[-1,-5,2],[[0,2],[1,1]]]

expected: [-5,-5]

Starter codePython

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

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