Process a stream of obstacle queries and report the k-th nearest obstacle after each update.
You are given a sequence of queries about obstacles placed along a one-dimensional line. Each query adds one obstacle at a new position, and after processing the query you must report the distance of the k-th nearest obstacle from the origin among all obstacles seen so far.
If fewer than obstacles have been seen, report the nearest distance according to the problem’s query rules for that state. The intended challenge is to maintain the top nearest obstacles efficiently as queries arrive one by one.
Solve the problem online: after every query, update the data structure and return the required answer for the current prefix of queries.
Input Format
- The input consists of an integer and a list of obstacle queries.
- Each query represents a newly added obstacle position.
- Queries must be processed in order, and an answer is produced after every query.
Output Format
- Return an array of integers.
- The -th value is the answer after processing the -th query.
Constraints
- 1 <= k <= number of queries
- Query count can be large enough that an approach is not ideal
- Positions and distances are assumed to fit in standard integer types
Example 1
Input
k = 3 queries = [5, 2, 8, 1, 4]
Output
[5, 2, 5, 2, 2]
Explanation
After each insertion, the nearest distances seen so far are tracked. The 3rd nearest among the processed obstacles determines the answer once at least 3 obstacles exist; before that, the answer follows the query-state rule for smaller prefixes.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.