Kth Smallest in a Range

Problem

Answer queries [left, right, k] returning the k-th smallest value in the inclusive subarray nums[left..right].

Build a merge sort tree over the array, then binary search the answer and count how many elements in the range are at most a candidate using the tree. Return the answers in query order.

Hint

Counting elements at most a candidate over a range lets you binary search the value.

Test cases

case 1

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

expected: [6,1,3]

case 2

in: [[1],[[0,0,1]]]

expected: [1]

case 3

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

expected: [3]

case 4

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

expected: [5,2]

case 5

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

expected: [2]

Starter codePython

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

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