Kth smallest dynamic set
You maintain a dynamic set of integers in a BST and must answer order-statistic queries efficiently. Given a list of operations, process them in order: ['insert', x] adds x to the set (duplicates are ignored), and ['kth', k] asks for the k-th smallest value currently in the set (1-indexed; if k exceeds the set size, the answer is -1). Return the list of answers, one per 'kth' query, in order. Your solution must support each operation in average time better than O(size) by augmenting the BST with subtree sizes.
Implement
dynamic_kth_smallest(ops: list[list]) → list[int]Examples
in
[[["insert",5],["insert",3],["insert",8],["kth",1],["kth",2],["kth",3]]]out[3,5,8]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[[["insert",5],["insert",3],["insert",8],["kth",1],["kth",2],["kth",3]]][3,5,8]not run yetsample