Sparse Table Block Selection

Problem

A range-minimum sparse-table query on [l, r] uses k = floor(log2(r - l + 1)) and compares the two overlapping blocks of length 2^k that start at l and at r - 2^k + 1. Given nums and queries of [l, r] pairs, return [k, left_start, right_start] for each query in order. Assume every query is valid and nums is non-empty.

Hint

Precompute floor(log2) for every length once, then each query is O(1).

Test cases

case 1

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

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

case 2

in: [[10,20,30,40,50],[[0,4],[1,3],[2,2]]]

expected: [[2,0,1],[1,1,2],[0,2,2]]

case 3

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

expected: [[0,0,0]]

Starter codePython

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

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