Count Pairs of Points Within 2 Units on Both Axes

You are given a list of points on a plane with integer coordinates. Two points intersect when their x-coordinates differ by at most 2 and their y-coordinates also differ by at most 2. Return the number of pairs of points that intersect.

Function Signature

def count_intersecting_pairs(points: list[list[int]]) -> int:

Rules

• Each point is given as [x, y].
• Points i and j intersect when abs(x_i - x_j) <= 2 and abs(y_i - y_j) <= 2; both bounds are inclusive.
• Count unordered pairs of different indices i < j, each pair once. A point is never paired with itself.
• Points may repeat: two points at the same coordinates are different points, and they intersect.

Constraints

• 1 <= len(points) <= 10^5
• -10^9 <= x, y <= 10^9
• the answer can reach n * (n - 1) / 2, about 5 * 10^9 when all points coincide, which exceeds 2^31 - 1; return it as an exact integer

Examples

Example 1

Input: points = [[0, 0], [2, 2], [3, 0], [5, 5]]
Output: 2

[0, 0] and [2, 2] differ by 2 on both axes, and [2, 2] and [3, 0] differ by 1 and 2. Every other pair differs by more than 2 on at least one axis.

Example 2

Input: points = [[1, 1], [1, 1], [1, 4]]
Output: 1

The two copies of [1, 1] intersect; [1, 4] is 3 away from both on the y-axis.

Example 3

Input: points = [[0, 0]]
Output: 0

A single point forms no pairs.