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.
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.
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.
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.
Time Complexity: O(n log n), due to sorting the array.
Space Complexity: O(1), since it uses constant space for pointers.
| 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. |
| 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 |
🔴 2857. Count Pairs of Points With Distance k II XOR II Biweekly Contest 113 II Leetcode 2857 • Aryan Mittal • 1,951 views views
Watch 8 more video solutions →Practice Count Pairs of Points With Distance k with our built-in code editor and test cases.
Practice on FleetCode