Watch 9 video solutions for Count Pairs of Points With Distance k, a medium level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Aryan Mittal has 1,951 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane.
We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.
Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.
Example 1:
Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5 Output: 2 Explanation: We can choose the following pairs: - (0,1): Because we have (1 XOR 4) + (2 XOR 2) = 5. - (2,3): Because we have (1 XOR 5) + (3 XOR 2) = 5.
Example 2:
Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0 Output: 10 Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.
Constraints:
2 <= coordinates.length <= 500000 <= xi, yi <= 1060 <= k <= 100Problem Overview: You receive a list of 2D points [x, y] and an integer k. A pair of points is valid when (x1 XOR x2) + (y1 XOR y2) = k. The task is to count how many unique pairs satisfy this condition without double counting.
The expression mixes coordinate math with XOR operations, which makes typical distance formulas or geometric tricks unusable. The key observation: if (x1 XOR x2) + (y1 XOR y2) = k, then for any possible value dx = x1 XOR x2, the corresponding dy must be k - dx. That reduces the search space dramatically.
Approach 1: Hash Map Enumeration (O(n * k) time, O(n) space)
Use a frequency hash table that stores previously seen points. Iterate through each point (x, y). For every possible value dx from 0 to k, compute dy = k - dx. If x1 XOR x2 = dx, then the matching x-coordinate must be x2 = x ^ dx. Similarly, y2 = y ^ dy. Check the hash map to see if this target point already exists and add its frequency to the answer. After processing all dx splits, insert the current point into the map.
This works because XOR is reversible: if a XOR b = c, then b = a XOR c. Instead of scanning all previous points, you directly compute the only coordinates that could satisfy the equation. The loop over 0..k bounds the search. This approach combines bit manipulation with constant‑time hash lookups.
Approach 2: Sorting and Two-Pointer Technique (O(n log n + n * k) time, O(1) extra space)
Another strategy sorts the points (typically by x, then y). Sorting helps process candidate pairs in a predictable order and avoids repeated map allocations. For each point, iterate through possible dx values and compute the target x-coordinate x ^ dx. Since the array is sorted, you can restrict the search to the subrange where this x-coordinate appears. Within that range, use a two-pointer style scan or binary search to check candidate y values that satisfy y1 XOR y2 = k - dx.
The idea is to reduce unnecessary comparisons by leveraging ordering instead of hashing. In practice, this approach is slightly more complex but avoids additional memory. It still relies on the same XOR decomposition of the distance formula.
Recommended for interviews: The hash map approach is the expected solution. It shows you recognize the XOR reversibility trick and use a constant-time lookup structure. Mentioning the brute force O(n^2) pair scan demonstrates baseline reasoning, but implementing the hash-based method shows strong command of array iteration, hashing, and bitwise manipulation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small input sizes or when first reasoning about the problem |
| Hash Map Enumeration | O(n * k) | O(n) | General case; fastest and simplest interview solution |
| Sorting + Two-Pointer Search | O(n log n + n * k) | O(1) | When minimizing extra memory or working with pre-sorted data |