FastPrep
Problem

Minimum Euclidean Plate Collection Time

Learn this problem
Uber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

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.

Function

getMinEuclideanTime(n: int, d: int, x: int[], y: int[]) → int

Examples

Example 1

n = 4d = 1x = [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.

Example 2

n = 3d = 2x = [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

Constraints:

  • 1 <= n <= 1000
  • 0 <= d <= 10000
  • 0 <= x[i], y[i] <= 10000
  • 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
checking account