Tap here to switch tabs
Problem
Submissions

Problem: K-th Nearest Obstacle Queries

K-th Nearest Obstacle Queries adds obstacles to an infinite plane one at a time. After each placement, return the Manhattan distance of the k-th closest obstacle to the origin, or -1 if fewer exist.

Statement

There is an infinite 2D2 {D} plane where you are given a 2D2 {D} integer array queries, where each queries[i] = [x, y] represents an obstacle placed at the coordinate (x,y)(x, y). You are also given an integer k.

Initially, there are no obstacles on the plane. For each query, an obstacle is placed at the specified coordinate.

The distance of an obstacle at (x,y)(x, y) from the origin (0,0)(0, 0) is defined as its Manhattan distance, which is ∣x∣+∣y∣|x| + |y|.

Return an integer array results of length equal to queries.length, where results[i] represents the distance of the kthk^{ {th}} nearest obstacle to the origin after processing the ithi^{ {th}} query. If there are fewer than k obstacles present after a query, results[i] should be −1-1.

Constraints:

  • 1≤1 \leq queries.length ≤2×105\leq 2 \times 10^5

  • All queries[i] are unique.

  • −109≤-10^9 \leq queries[i][0], queries[i][1] ≤109\leq 10^9

  • 1≤1 \leq k ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: K-th Nearest Obstacle Queries

K-th Nearest Obstacle Queries adds obstacles to an infinite plane one at a time. After each placement, return the Manhattan distance of the k-th closest obstacle to the origin, or -1 if fewer exist.

Statement

There is an infinite 2D2 {D} plane where you are given a 2D2 {D} integer array queries, where each queries[i] = [x, y] represents an obstacle placed at the coordinate (x,y)(x, y). You are also given an integer k.

Initially, there are no obstacles on the plane. For each query, an obstacle is placed at the specified coordinate.

The distance of an obstacle at (x,y)(x, y) from the origin (0,0)(0, 0) is defined as its Manhattan distance, which is ∣x∣+∣y∣|x| + |y|.

Return an integer array results of length equal to queries.length, where results[i] represents the distance of the kthk^{ {th}} nearest obstacle to the origin after processing the ithi^{ {th}} query. If there are fewer than k obstacles present after a query, results[i] should be −1-1.

Constraints:

  • 1≤1 \leq queries.length ≤2×105\leq 2 \times 10^5

  • All queries[i] are unique.

  • −109≤-10^9 \leq queries[i][0], queries[i][1] ≤109\leq 10^9

  • 1≤1 \leq k ≤105\leq 10^5