Count Pairs of Points Within 2 Units on Both Axes
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
Input: points = [[0, 0]]
Output: 0
```
A single point forms no pairs.
Overview: A coding question that asks how many pairs of points intersect, where two points intersect when both their x-coordinates and their y-coordinates differ by at most 2. It tests counting unordered pairs with duplicate points, inclusive bounds and scaling to 100,000 points with large coordinates.
Read the full Capital One Software Engineer interview experience this question came from
You are given a list `points` of points on a plane with integer coordinates; each point is given as `[x, y]`. Two points **intersect** when their x-coordinates differ by at most 2 **and** their y-coordinates also differ by at most 2: points `i` and `j` intersect when `abs(x_i - x_j) <= 2` and `abs(y_i - y_j) <= 2`. Both bounds are inclusive.
Return the number of pairs of points that intersect. 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.
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 (`long` in Java, `long long` in C++). Each coordinate fits in a 32-bit signed integer.
**Example 1**
```text
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**
```text
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.
**Constraints**
- `1 <= len(points) <= 10^5`
- each `points[i]` is a pair `[x, y]` of integers
- `-10^9 <= x, y <= 10^9`
- the answer is at most `n * (n - 1) / 2` (about `5 * 10^9`), which can exceed `2^31 - 1`; return it as an exact integer
Constraints
- 1 <= len(points) <= 10^5
- each points[i] is a pair [x, y] of integers
- -10^9 <= x, y <= 10^9
- the answer is at most n * (n - 1) / 2 (about 5 * 10^9 when all points coincide), which exceeds 2^31 - 1; return it as an exact integer (long in Java, long long in C++)
Examples
Input: ([[0, 0], [2, 2], [3, 0], [5, 5]],)
Expected Output: 2
Explanation: Source example 1: [0, 0]-[2, 2] differ by 2 on both axes and [2, 2]-[3, 0] by 1 and 2; every other pair exceeds 2 on some axis.
Input: ([[1, 1], [1, 1], [1, 4]],)
Expected Output: 1
Explanation: Source example 2: the two coincident [1, 1] points intersect; [1, 4] is 3 away from both on the y-axis.
Hints
- Every point that can intersect a given point has integer coordinates within 2 of it on both axes, so it lies inside a 5 by 5 block of coordinates centered on that point.
- Points at identical coordinates all intersect each other: work out how many pairs a group of k coincident points contributes, without pairing a point with itself.
- Count each unordered pair exactly once, and remember both bounds are inclusive: a difference of exactly 2 counts, a difference of 3 does not.