FastPrep
Problem

Minimum Euclidean Plate Collection Time

UberFULLTIMEOA
See Uber hiring insights

You are given n plates placed on a 2D grid. Plate i is located at coordinate (x[i], y[i]). Each plate has the same magnetic attraction power d.

Two plates are directly connected if the Euclidean distance between them is less than or equal to d. Connectivity is transitive: if a plate is connected directly or indirectly to another plate, collecting one plate collects the entire connected component in 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 = 4
d = 1
x = [0, 0, 1, 2]
y = [0, 1, 0, 2]
return = 2

The first three plates form one connected component because adjacent distances are at most 1. The plate at (2,2) is separate, so two seconds are needed.

02 · Example 2
n = 3
d = 2
x = [0, 3, 6]
y = [0, 0, 0]
return = 3

Each pair of neighboring plates is distance 3 apart, which is greater than d, so each plate is collected separately.

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