Point update and find R-th minimum element
Filed under Deutsche Bank
Free read 1 of 3Confirm 0-indexed or 1-indexed for both array positions and R. Check if updates and queries can be interleaved.
The question
Given an array of size S, process N queries where each query updates the element at index M to value P, and then outputs the R-th smallest element of the modified array.
Constraints
- 1 <= S, N <= 10^5
- 1 <= R <= S
- Time limit requires sub-quadratic per-query performance
Examples
- Input
- arr = [3, 1, 4], queries = [[2, 5, 2]]
- Output
- [3]
- Why
- Update index 2 (0-indexed) to 5, array becomes [3, 5, 4]. The 2nd smallest element (1-indexed) is 4.
Approach
Confirm 0-indexed or 1-indexed for both array positions and R. Check if updates and queries can be interleaved.
Modify the array at index M, create a sorted copy, and retrieve the R-th element. Complexity is O(N * S log S), which fails for large S and N.
Use a data structure like a Fenwick tree (Binary Indexed Tree) over coordinate-compressed values, or an Order Statistic Tree / Balanced BST (like AVL/Red-Black or multiset in C++) to maintain element counts and query the R-th order statistic efficiently in O(log S) per query.
R = 1 (minimum) or R = S (maximum), updating elements to values already present in the array.
Tips
- What they are testing: Test updates to boundaries, extreme values of R (1 and S), and repeated identical values.
- Common mistake: Re-sorting the array or using a linear search after every single update, resulting in O(N * S log S) TLE.
Related Deutsche Bank questions
Collected from public candidate posts and coding forums. Updated Nov 2026.