NewProject Coding is here — build features and fix bugs in real codebases with an AI assistantSee what's new

You are given a list of ball coordinates balls, where balls[i] = [xix_i, yiy_i] represents the position of the ithi^{\text{th}} ball on a 2D plane. Two balls connect if they are in the same row (same y-coordinate) or the same column (same x-coordinate), and their distance along the shared axis is at most d. Distance is measured as the absolute difference of coordinates along that axis.

You can remove one ball at a time. When you remove a ball, it and all balls connected to it through chain reactions are removed. Return the minimum number of operations needed to remove all balls.

Constraints:

  • 1 ≤ balls.length ≤ 10410^4
  • −104-10^4 ≤ xix_i, yiy_i ≤ 10410^4
  • 0 ≤ d ≤ 10410^4
  • All ball coordinates are unique (no two balls at the same position)

Example 1:

Input: balls = [[0, 0], [0, 2], [0, 4], [5, 0]], d = 2 Output: 2 Explanation: The chain reactions are analyzed as follows:

  • Ball at (0, 0) and ball at (0, 2) are in the same column (x=0), and distance is 2 ≤ d=2, so they connect.
  • Ball at (0, 2) and ball at (0, 4) are also in the same column, and the distance is 2, so they connect.
  • Therefore, (0, 0), (0, 2), and (0, 4) form one connected component through transitive connections. Ball at (5, 0) is not connected to any other ball. We need 2 removals: one for the vertical chain and one for the isolated ball.

Example 2:

Input: balls = [[1, 1], [3, 1]], d = 2 Output: 1

Example 3:

Input: balls = [[1, 1], [1, 2], [2, 2], [2, 3]], d = 1 Output: 1


Accepted
1.7k/3.2k
Acceptance Rate52.2%
Test Cases
Input
balls =
d =
Output
Expected