โ† Deutsche Bank questions
CodingReported in a candidate post, Aug 2019

Point update and find R-th minimum element

Filed under Deutsche Bank

Free read 1 of 3

Confirm 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

  1. Confirm 0-indexed or 1-indexed for both array positions and R. Check if updates and queries can be interleaved.

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.