K-th Smallest Remaining Even Integer in Subarray Queries - Solution & Explanation

Problem Overview: You receive an array and multiple queries [l, r, k]. For each query, consider the elements inside the subarray and keep only the even numbers. From those remaining values, return the k-th smallest element. If fewer than k even numbers exist, return an indicator such as -1.

Approach 1: Filter + Sort Per Query (Brute Force) (Time: O(q * n log n), Space: O(n))

The direct method iterates through every query and scans the range [l, r]. Collect only even numbers into a temporary list, sort that list, and return the k-th element if it exists. The logic is simple: iterate through the subarray, apply a modulus check num % 2 == 0, then sort. This approach works for small inputs but becomes slow when the array and query count grow because each query repeats the same scanning and sorting work.

Approach 2: Pre-filter Evens + Binary Search on Positions (Time: O(q log n + m log m), Space: O(m))

Store only the even numbers along with their indices. Maintain two arrays: positions and values. For a query [l, r], use binary search to find the first and last even indices that fall inside the range. Extract the corresponding values and determine the k-th smallest. Sorting each subset still costs time, but the search space shrinks significantly when the array contains many odd numbers. This technique combines index filtering with binary search.

Approach 3: Merge Sort Tree / Range Order Statistics (Time: O((n + q) log² n), Space: O(n log n))

Build a segment tree where each node stores a sorted list of the even numbers present in that segment. Odd values are ignored during construction. To answer a query, traverse the segment tree nodes covering [l, r]. Instead of merging arrays at query time, perform a value-based binary search: guess a candidate value and count how many even numbers ≤ that value exist across the relevant nodes. Each count query uses binary search inside the node lists, producing O(log² n) per query. This technique effectively turns the problem into a range order-statistic query.

Approach 4: Wavelet Tree / Order Statistic Structure (Time: O((n + q) log n), Space: O(n log n))

A wavelet tree or advanced order statistic tree can directly answer "k-th smallest in range" queries. Build the structure using only even values (or mark odds so they are skipped). Each query walks down the tree while maintaining rank counts inside [l, r]. This reduces the query complexity to roughly O(log n), making it the fastest scalable solution for large inputs.

Recommended for interviews: Start by describing the brute-force scan and sort approach to show understanding of the query requirement. Then move quickly to the segment tree or merge sort tree solution. Interviewers usually expect a range order-statistic structure because it demonstrates familiarity with range queries, binary search on answer, and advanced data structures.