Archive Kth Smallest Problem

Archive Kth Smallest Problem — ExecCode Hard DSA Practice

Solve the Archive Kth Smallest problem on ExecCode. Free online hard DSA practice in Searching & Sorting. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A dusty archive stores integers in a row. Historians ask: in the closed range from l to r, what is the k-th smallest value (0-based)? A persistent segment tree (or a merge-sort tree) stores every prefix's frequency tree so a range is two roots subtracted. Each query is [l, r, k] with 0-based indices. Return that order statistic, or -1 if k is out of range. You are given: arr — the row queries — [l, r, k] Return one value per query. Duplicates are kept: the 0-th and 1-st smallest may be equal.

Examples

Input {'arr': [4, 1, 3, 2], 'queries': [[0, 3, 0], [0, 3, 3], [1, 2, 1]]}; Output [1, 4, 3]. Input {'arr': [7], 'queries': [[0, 0, 0], [0, 0, 1]]}; Output [7, -1]. Input {'arr': [5, 5, 5], 'queries': [[0, 2, 2]]}; Output [5]

Constraints

l <= r k is 0-based inside that slice

Practice Archive Kth Smallest free on ExecCode. Browse DSA problems, topic map, and placement guides.