LeetCode Problem 2857

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation

Solution

LeetCode 2857 - Count Pairs of Points With Distance k

Problem Understanding

We are given a list of 2D points, where each point is represented as [x, y], and an integer k.

The distance between two points is not the usual Euclidean or Manhattan distance. Instead, it is defined as:

$$(x_1 \oplus x_2) + (y_1 \oplus y_2)$$

where ⊕ denotes the bitwise XOR operation.

Our task is to count how many pairs of indices (i, j) satisfy:

• i < j
• The XOR distance between the corresponding points equals exactly k

The input size is important. We may have up to 50,000 points, making an O(n²) comparison of all pairs impossible.

The coordinates themselves can be as large as 10^6, but the crucial observation is that k ≤ 100, which is extremely small compared to the coordinate range. This constraint is what makes an efficient solution possible.

Several edge cases are worth noting:

• Multiple identical points may exist.
• k = 0, meaning both XOR values must be zero.
• Large coordinate values are allowed.
• Many duplicate coordinates may appear.
• The answer can be very large, potentially approaching n(n-1)/2, so we must accumulate counts carefully.

Approaches

Brute Force

The most direct approach is to examine every pair of points.

For every pair (i, j):

1. Compute coordinates[i][0] XOR coordinates[j][0].
2. Compute coordinates[i][1] XOR coordinates[j][1].
3. Add the two results.
4. If the sum equals k, increment the answer.

This method is clearly correct because it checks every possible pair exactly once.

However, with n = 50,000, the number of pairs is:

$$\frac{50000 \cdot 49999}{2}$$

which is approximately 1.25 billion comparisons. This is far too slow.

Key Insight

Suppose we are currently processing a point (x, y).

For a previous point (px, py) to form a valid pair, we need:

$$(x \oplus px) + (y \oplus py) = k$$

Let:

$$dx = x \oplus px$$

Then:

$$dy = k - dx$$

Since dx + dy = k, we can enumerate every possible split of k:

$$dx = 0,1,2,\ldots,k$$

and

$$dy = k-dx$$

For a chosen (dx, dy), the required previous point is uniquely determined:

$$px = x \oplus dx$$

$$py = y \oplus dy$$

Therefore, while processing (x, y), we can ask:

"How many previous points equal (x XOR dx, y XOR dy)?"

A hash map can answer this in O(1) time.

Because k ≤ 100, there are only k + 1 ≤ 101 possible splits to check for every point.

This transforms the problem into an efficient hash-table counting problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair explicitly
Optimal	O(nk)	O(n)	Enumerates all XOR splits of k and uses a hash map

Since k ≤ 100, O(nk) is effectively linear.

Algorithm Walkthrough

1. Create a hash map frequency that stores how many times each point has already appeared.
2. Initialize answer = 0.
3. Process points one by one from left to right.
4. For the current point (x, y), enumerate every possible value:

$$dx = 0 \ldots k$$ 5. Compute:

$$dy = k - dx$$ 6. The only point that could produce these XOR values is:

$$targetX = x \oplus dx$$

$$targetY = y \oplus dy$$ 7. Look up (targetX, targetY) in the hash map. Every occurrence corresponds to a previously seen point whose distance from (x, y) is exactly k. 8. Add that frequency to the answer. 9. After all splits have been checked, insert the current point into the hash map. 10. Continue until all points have been processed. 11. Return the final answer.

Why it works

For any valid pair, let:

$$dx = x_1 \oplus x_2$$

$$dy = y_1 \oplus y_2$$

Since the pair's distance equals k, we have:

$$dx + dy = k$$

The algorithm enumerates every possible split (dx, dy) satisfying this equation. For each split, XOR's self-inverse property guarantees that the corresponding partner point is uniquely:

$$(x \oplus dx,; y \oplus dy)$$

Therefore every valid previous point is counted exactly once, and no invalid point can satisfy the lookup condition. Because points are inserted only after processing, every pair is counted exactly once with i < j.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        frequency = defaultdict(int)
        answer = 0

        for x, y in coordinates:
            for dx in range(k + 1):
                dy = k - dx

                target_x = x ^ dx
                target_y = y ^ dy

                answer += frequency[(target_x, target_y)]

            frequency[(x, y)] += 1

        return answer

The implementation maintains a hash map whose keys are coordinate pairs and whose values are occurrence counts.

For every point, we enumerate all possible values of dx from 0 through k. Once dx is fixed, dy is determined as k - dx.

Using the XOR inverse property, we compute the exact coordinates that a previous point must have in order to create that XOR contribution. The hash map immediately tells us how many such points have already appeared.

After counting all matching previous points, we insert the current point into the map. This guarantees that each pair is counted once and only once.

Go Solution

func countPairs(coordinates [][]int, k int) int {
	frequency := make(map[[2]int]int)
	answer := 0

	for _, point := range coordinates {
		x, y := point[0], point[1]

		for dx := 0; dx <= k; dx++ {
			dy := k - dx

			target := [2]int{x ^ dx, y ^ dy}
			answer += frequency[target]
		}

		frequency[[2]int{x, y}]++
	}

	return answer
}

The Go solution follows the exact same logic as the Python version.

A fixed-size array [2]int is used as the map key because arrays are comparable and can be used directly as map keys. Since the maximum possible answer is approximately 1.25 billion, the standard Go int type is sufficient on LeetCode platforms.

Worked Examples

Example 1

coordinates = [[1,2],[4,2],[1,3],[5,2]]
k = 5

Possible splits:

dx	dy
0	5
1	4
2	3
3	2
4	1
5	0

Process (1, 2)

Hash map is empty.

No matches found.

Insert:

(1,2): 1

Answer = 0

Process (4, 2)

Checking splits:

dx	dy	Required point
5	0	(1,2)

The map contains (1,2) once.

Answer becomes 1.

Insert:

(1,2): 1
(4,2): 1

Process (1, 3)

No required point exists in the map.

Answer remains 1.

Insert (1,3).

Process (5, 2)

Checking splits:

dx	dy	Required point
4	1	(1,3)

The map contains (1,3) once.

Answer becomes 2.

Final answer:

2

Example 2

coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]]
k = 0

Only one split exists:

dx	dy
0	0

Process points:

Point Number	Existing Copies	New Pairs
1	0	0
2	1	1
3	2	2
4	3	3
5	4	4

Total:

0 + 1 + 2 + 3 + 4 = 10

Answer:

10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nk)	For each point we enumerate all k+1 splits
Space	O(n)	Hash map may store every distinct point

Since k ≤ 100, the inner loop performs at most 101 iterations. Therefore the practical running time is approximately 101 × n, which is effectively linear in the number of points.

Test Cases

from typing import List

s = Solution()

assert s.countPairs([[1,2],[4,2],[1,3],[5,2]], 5) == 2  # example 1

assert s.countPairs(
    [[1,3],[1,3],[1,3],[1,3],[1,3]],
    0
) == 10  # example 2

assert s.countPairs([[0,0],[0,0]], 0) == 1  # smallest duplicate pair

assert s.countPairs([[0,0],[1,1]], 0) == 0  # different points, k=0

assert s.countPairs([[0,0],[5,0]], 5) == 1  # XOR only in x-coordinate

assert s.countPairs([[0,0],[0,5]], 5) == 1  # XOR only in y-coordinate

assert s.countPairs([[1,1],[2,2],[3,3]], 100) == 0  # no valid pairs

assert s.countPairs([[7,9],[7,9],[7,9]], 0) == 3  # C(3,2)

assert s.countPairs([[1000000,1000000],[1000000,1000000]], 0) == 1  # large coordinates

assert s.countPairs([[0,0],[1,0],[2,0],[3,0]], 1) == 3  # multiple matches

Test Summary

Test	Why
[[1,2],[4,2],[1,3],[5,2]], k=5	Official example
Five identical points, k=0	Official example with duplicates
[[0,0],[0,0]]	Smallest duplicate case
[[0,0],[1,1]], k=0	Different points should not match
[[0,0],[5,0]], k=5	XOR contribution only from x
[[0,0],[0,5]], k=5	XOR contribution only from y
Large coordinates	Verifies coordinate magnitude does not matter
Three identical points	Checks combinatorial counting
No valid pair	Verifies zero-result scenario
Multiple matches with k=1	Tests repeated successful lookups

Edge Cases

k = 0

When k is zero, the only possible split is (dx, dy) = (0, 0). A pair is valid only if both coordinates are identical, because XOR equals zero only when the operands are equal. The implementation naturally handles this because the loop runs once and looks up the exact same coordinate.

Many Duplicate Points

If a coordinate appears many times, a naive implementation might accidentally double count pairs. The hash map stores frequencies of previously seen points, and each new occurrence adds exactly the number of earlier occurrences. This correctly computes combinations such as C(n,2) without overcounting.

Large Coordinate Values

Coordinates may be as large as 10^6. An approach based on coordinate compression or large arrays would be inconvenient. The solution uses a hash map keyed by coordinate pairs, so coordinate magnitude has no effect on correctness or memory usage beyond storing the key itself.

Maximum Input Size

With 50,000 points, an O(n²) solution is infeasible. The algorithm performs at most 50,000 × 101 ≈ 5 million hash lookups, which easily fits within typical LeetCode limits. The space usage also remains manageable because each distinct point is stored once in the hash map.