Order Statistics via Sorted List

Problem

Maintain a sorted list supporting k-th smallest and rank queries.

operations contains "insert" (values[i] is the value), "kth" (values[i] is the 1-based rank), or "count_less" (values[i]). insert records None, kth returns the element at that rank or None when out of range, and count_less returns how many stored values are strictly smaller.

Return the list of recorded results.

Hint

bisect.insort keeps the list ordered, and bisect_left gives the count of smaller elements.

Test cases

case 1

in: [["insert","insert","insert","kth","kth","count_less"],[5,1,3,1,3,3]]

expected: [null,null,null,1,5,1]

case 2

in: [["kth"],[1]]

expected: [null]

case 3

in: [["insert","insert","count_less"],[2,2,2]]

expected: [null,null,0]

case 4

in: [["insert","kth","insert","kth"],[10,1,5,2]]

expected: [null,10,null,10]

Starter codePython

def sorted_list_ops(operations, values):
    # Your code here
    pass

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