FastPrep
Problem

Minimum Plate Collection Time

UberFULLTIMEOA
See Uber hiring insights

You are given n plates placed on a 2D plane. Plate i is at coordinate (x[i], y[i]).

Two plates are connected if they lie in the same row or the same column and the distance between them is at most d. Connectivity is transitive: if plate a is connected to plate b, and plate b is connected to plate c, then collecting one of them collects all plates in that connected component during the same second.

You may choose one uncollected plate per second. Return the minimum number of seconds required to collect all plates.

Examples
01 · Example 1
n = 3
d = 1
x = [0, 2, 1]
y = [0, 1, 2]
return = 3

No pair of plates lies in the same row or column within distance 1, so all three plates are separate connected components.

Constraints
  • 1 <= n <= 10^5
  • 0 <= d <= 10^9
  • 0 <= x[i], y[i] <= 10^9
More Uber problems
drafts saved locally
public int getMinTime(int n, int d, int[] x, int[] y) {
  // write your code here
}
n3
d1
x[0, 2, 1]
y[0, 1, 2]
expected3
sign in to submit