357. Kth Smallest Element in a Range

Given an array of n integers and q queries, each giving a range [l, r] (1-indexed, inclusive) and an integer k, find the k-th smallest element within arr[l..r] for every query. Print all q answers, in order, space-separated, on a single line.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains an integer q, the number of queries. The next q lines each contain three integers l, r, k. Output: Print all q answers, in order, space-separated on a single line.

1 <= n <= 10^5, 1 <= q <= 10^4, 1 <= l <= r <= n, 1 <= k <= r - l + 1

Choosing between the simple fresh-sort-per-query approach and building a merge-sort tree upfront is a genuine ENGINEERING TRADEOFF based on the actual constraints (how many queries, how large the ranges) - recognizing when the added complexity of a merge-sort tree is actually worth it is as important as knowing the technique exists.

Given an array and several range queries, find the kth smallest element within each specified range. Brute force: For every query, sort the relevant slice fresh - this costs O(r*log r) per query (where r is the range size), giving a total that can be slow when there are many queries on large ranges, though it's simple and completely correct for smaller constraints. Optimised: Building a MERGE-SORT TREE once upfront (where each segment-tree node stores its own range's elements pre-sorted, built during a standard merge-sort-style construction) lets each query be answered by combining O(log n) pre-sorted node ranges and binary searching across them for the kth smallest - reducing each query's cost from O(r log r) down to O(log² n), independent of the range's size.

For each query, scan the subarray from l to r while maintaining a max-heap that never holds more than k elements: push each element, and whenever the heap exceeds size k, pop off the current largest. Once the whole subarray has been scanned, the top of the heap holds the k-th smallest value for that query. This is correct because keeping only the k smallest elements seen so far at all times guarantees the heap's maximum is exactly the k-th smallest overall once scanning finishes, and it avoids the full sort of the brute force by touching each element with only a small O(log k) heap operation. Time: O(q * n log k) Space: O(k)

Preprocess the array once into a merge sort tree: a segment tree where every node stores the sorted list of elements in the range it covers, built bottom-up by merging children's sorted lists, in O(n log n) total. To answer a query, binary search over the possible answer values, and for each candidate value count how many elements in [l, r] are less than or equal to it by visiting the O(log n) segment tree nodes covering that range and binary searching within each node's sorted list; adjust the search bounds until the exact k-th smallest value is pinned down. This is correct because the merge sort tree gives fast counting of elements below any threshold for an arbitrary range, and combining that with binary search on the answer avoids ever re-sorting a range from scratch, answering each query in time only logarithmic in both the array size and value range. Time: O(n log n + q * log^2 n) Space: O(n log n)

For every query, extract the elements from index l to r into a fresh array, sort that array, and return the element at position k-1. This is correct because sorting any subarray puts its elements in order, making the k-th smallest trivial to read off directly, but sorting is redone completely from scratch for every one of the q queries even when ranges overlap heavily. Time: O(q * n log n) Space: O(n)

1. The straightforward approach: for each query, extract the relevant slice of the array and sort it fresh, then index directly into position k-1. 2. For MANY queries on a large array, a more advanced structure like a merge-sort tree (a segment tree where every node stores its range's elements pre-sorted) answers each query in O(log² n) once built. 3. An even more advanced persistent segment tree can answer each query even faster.

Time: O(n log n) to build the merge-sort tree once, then O(log² n) per query; O(r log r) per query with the simpler fresh-sort approach (r being the query range's size), acceptable when there are few queries or small ranges. Space: O(n log n), for the merge-sort tree structure (storing pre-sorted arrays at every node).

Test a query with l = r (single element, k must be 1), a query spanning the full array (l=1, r=n), and n = 10^5 with q = 10^4 for performance.

Be ready to mention that for TRULY large-scale scenarios (huge n and huge q), a persistent segment tree over the VALUES (rather than array positions) provides an even more elegant O(log n) per-query solution - a strong signal of awareness of more advanced structures beyond the immediately obvious approach.