Count Pairs of Points With Distance k - Solution & Explanation
Problem Statement
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 <= 100
Approach Overview
Problem 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 1: Approach 1: Using a Hash Map
This approach utilizes a hash map to store elements and their indices for quick lookup. The main idea is to iterate through the given data structure (e.g., list or array) and check if the desired complement exists in the hash map. This method improves efficiency by reducing the need for nested iterations.
This C solution involves using a simple hash table implementation with an array of structs, where each struct stores a key-value pair representing an integer from the input and its index. As we iterate over the input, we check for the target complement in the hash table and return the indices if a pair is found.
Complexity
Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once and use a secondary loop inside (hash checking is O(1) on average).
Space Complexity: O(n), due to the hash table storage.
Approach 2: Approach 2: Sorting and Two-Pointer Technique
This approach involves sorting the input, then using a two-pointer technique to find pairs. The idea is to sort the array and use two indices starting from both ends of the array, moving inwards based on comparison with the target sum. This approach avoids using extra space for hash tables.
This solution sorts the array initially. Using two pointers, one starting at the beginning and another at the end, we adjust their positions based on their sum relative to the target. Sorting facilitates efficient checks with a time complexity benefit.
Complexity
Time Complexity: O(n log n), due to sorting the array.
Space Complexity: O(1), since it uses constant space for pointers.
Approach 3: Hash Table + Enumeration
We can use a hash table cnt to count the occurrence of each point in the array coordinates.
Next, we enumerate each point (x_2, y_2) in the array coordinates. Since the range of k is [0, 100], and the result of x_1 \oplus x_2 or y_1 \oplus y_2 is always greater than or equal to 0, we can enumerate the result a of x_1 \oplus x_2 in the range [0,..k]. Then, the result of y_1 \oplus y_2 is b = k - a. In this way, we can calculate the values of x_1 and y_1, and add the occurrence of (x_1, y_1) to the answer.
The time complexity is O(n times k), and the space complexity is O(n). Here, n is the length of the array coordinates.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Hash Map | Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once and use a secondary loop inside (hash checking is O(1) on average). |
| Approach 2: Sorting and Two-Pointer Technique | Time Complexity: O(n log n), due to sorting the array. |
| Hash Table + Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
🔴 2857. Count Pairs of Points With Distance k II XOR II Biweekly Contest 113 II Leetcode 2857 • Aryan Mittal • 1,965 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Pairs of Points With Distance k easy or hard?
Count Pairs of Points With Distance k Python/Java solution
How to solve Count Pairs of Points With Distance k in O(n)?
What is the best approach for Count Pairs of Points With Distance k?
Is Count Pairs of Points With Distance k asked at Google/Amazon/Meta?
What data structure is used in Count Pairs of Points With Distance k?
What is the time complexity of Count Pairs of Points With Distance k?
Ready to solve this problem?
Practice Count Pairs of Points With Distance k with our built-in code editor and test cases.
Practice on FleetCode