Design a Class with Save and N-th Smallest Query
Design a class that supports two operations:
- `save(x)`: Store an integer $x$.
- `query(n)`: Return the $n$-th smallest integer currently stored.
Discuss multiple implementation approaches with different time complexity trade-offs, depending on the relative frequency of `save` vs. `query` operations.
**Constraints:**
-
\leq n \leq$ number of stored elements
- Elements may be duplicated
- Both operations will be called many times
**Example:**
```
save(5), save(3), save(8), save(1), save(3)
query(1) -> 1 (smallest)
query(2) -> 3 (2nd smallest)
query(3) -> 3 (3rd smallest, duplicate)
query(4) -> 5
```
Open the full interactive solver, hints, and worked solution →