This question evaluates the ability to model Euclidean-distance relations as a static connectivity graph and reason about the minimum number of activations needed to absorb all nodes, testing computational geometry and graph algorithms competency.
You are given n balls on a 2D plane, where ball i is at coordinate . You are also given a distance threshold d.
Two balls are considered to attract each other if their Euclidean distance is strictly less than . Attraction is transitive via a chain reaction: if ball A attracts B, and B attracts C, then starting from A will eventually cause A, B, and C to be absorbed into the same cluster.
Time proceeds in discrete steps. In each time step, you may choose one not-yet-absorbed ball to start the attraction process. In that step, all balls that are connected to it via a chain of attractions become absorbed.
Return the minimum number of time steps required so that all balls are absorbed.
Input:
Output:
Clarifications/Notes:
Example (illustrative): If the balls form 3 disconnected attraction groups, the answer is 3 because you must start the process once in each group.