# Count Pairs of Points With Distance k
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-pairs-of-points-with-distance-k)
Canonical: https://scaleengineer.com/dsa/problems/count-pairs-of-points-with-distance-k
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
---
## Problem
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 <= 50000`
* `0 <= xi, yi <= 106`
* `0 <= k <= 100`

# Approaches
## Brute Force
The brute-force approach is the most straightforward way to solve the problem. It involves iterating through every possible unique pair of points, calculating their distance as defined in the problem, and checking if this distance equals `k`. If it does, we increment a counter.
**Time:** O(N^2), where N is the number of points in the `coordinates` array. The nested loops lead to a quadratic number of comparisons, making this approach too slow for the problem's constraints (N up to 50000). · **Space:** O(1). We only use a few variables to keep track of indices and the count, so the space used is constant and does not depend on the input size.
**Pros:** Simple to understand and implement.; Requires minimal extra memory (constant space complexity).
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
We can implement this using two nested loops. The outer loop iterates through each point from the beginning of the array, and the inner loop iterates through the subsequent points. This ensures that we consider every pair `(i, j)` such that `i < j` exactly once, avoiding duplicate pairs and self-comparisons.

For each pair of points `(x1, y1)` and `(x2, y2)`, we compute the distance `(x1 ^ x2) + (y1 ^ y2)`. If this sum equals `k`, we've found a valid pair and increment our total count.

```java
class Solution {
    public int countPairs(int[][] coordinates, int k) {
        int n = coordinates.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = coordinates[i][0];
                int y1 = coordinates[i][1];
                int x2 = coordinates[j][0];
                int y2 = coordinates[j][1];
                
                if ((x1 ^ x2) + (y1 ^ y2) == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Get the number of points, `n`.
- Use a nested loop structure. The outer loop runs from `i = 0` to `n-2`.
- The inner loop runs from `j = i + 1` to `n-1`. This ensures each pair of points `(i, j)` is considered exactly once with `i < j`.
- Inside the inner loop, retrieve the coordinates for point `i` (`x1`, `y1`) and point `j` (`x2`, `y2`).
- Calculate the distance: `dist = (x1 XOR x2) + (y1 XOR y2)`.
- If `dist` is equal to `k`, increment the `count`.
- After the loops complete, return `count`.

## Optimized Approach using Hash Map
A much more efficient approach uses a hash map to optimize the search for pairs. The key idea is to rephrase the condition `(x1 ^ x2) + (y1 ^ y2) = k`. For a given point `(x1, y1)`, we need to find the number of other points `(x2, y2)` that satisfy this equation. We can iterate through all possible ways the integer `k` can be split into two non-negative integers, `i` and `k-i`. Then, for each split, we check if there's a point `(x2, y2)` such that `x1 ^ x2 = i` and `y1 ^ y2 = k - i`.
**Time:** O(N * k), where N is the number of points and `k` is the target distance. For each of the N points, we perform `k+1` lookups in the hash map. Since `k` is very small (<= 100), this complexity is effectively linear, i.e., O(N). · **Space:** O(U), where U is the number of unique points in the input. In the worst-case scenario where all N points are unique, the space complexity is O(N).
**Pros:** Very efficient, with a time complexity that is effectively linear in the number of points.; Handles the problem constraints with ease.; The logic is a clever application of hash maps and bitwise operations to solve a counting problem.
**Cons:** Requires extra space to store the hash map, which can be up to O(N) in the worst case where all points are unique.
### Explanation
We process the points one by one. For each point `p1 = (x1, y1)`, we query for partners that have been seen *before* it. This avoids double counting and satisfies the `i < j` condition implicitly.

The equation `(x1 ^ x2) + (y1 ^ y2) = k` can be broken down. Let `x_diff = x1 ^ x2` and `y_diff = y1 ^ y2`. We need `x_diff + y_diff = k`. Since `k` is small (<= 100), we can iterate through all possible values for `x_diff` from `0` to `k`. If `x_diff = i`, then `y_diff` must be `k - i`.

This means for a given `(x1, y1)`, we are looking for a point `(x2, y2)` where `x2 = x1 ^ i` and `y2 = y1 ^ (k-i)`. We can use a hash map to store the frequencies of points we have already visited. For each point, we iterate from `i = 0` to `k`, calculate the required `(x2, y2)`, and check our map for its frequency, adding it to our total count. After checking, we add the current point to the map.

To use a `Point` object as a key in a Java `HashMap`, we need to pack the two integer coordinates into a single primitive type like `long` for efficiency. Since `x` and `y` are at most `10^6`, they can each be represented by 20 bits. We can pack them into a 64-bit `long` by shifting one coordinate.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countPairs(int[][] coordinates, int k) {
        // Map to store frequency of points. Key is a packed long, value is count.
        Map<Long, Integer> pointCounts = new HashMap<>();
        int count = 0;
        
        for (int[] p : coordinates) {
            int x1 = p[0];
            int y1 = p[1];
            
            // Iterate through all possible values for the x-component of the distance.
            for (int i = 0; i <= k; i++) {
                int x_xor_val = i;
                int y_xor_val = k - i;
                
                // Calculate the coordinates of the target point (x2, y2).
                int x2 = x1 ^ x_xor_val;
                int y2 = y1 ^ y_xor_val;
                
                // Pack (x2, y2) into a long to use as a map key.
                // x, y <= 10^6, which is < 2^20. Shifting by 21 is safe.
                long key = ((long)x2 << 21) | y2;
                
                // Add the number of times we've seen this target point.
                count += pointCounts.getOrDefault(key, 0);
            }
            
            // Add the current point to the map for subsequent checks.
            long currentKey = ((long)x1 << 21) | y1;
            pointCounts.put(currentKey, pointCounts.getOrDefault(currentKey, 0) + 1);
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count = 0` and a hash map `pointCounts` to store the frequency of points encountered.
- Iterate through each point `(x1, y1)` in the `coordinates` array.
- For each point, iterate through all possible values of `i` from `0` to `k`.
  - Let `x_xor_val = i` and `y_xor_val = k - i`.
  - We are looking for a previously seen point `(x2, y2)` where `x2 = x1 ^ x_xor_val` and `y2 = y1 ^ y_xor_val`.
  - Calculate this target point `(x2, y2)`.
  - Create a unique key for the target point (e.g., by packing `x2` and `y2` into a `long`).
  - Look up this key in `pointCounts`. If it exists, add its value (frequency) to `count`.
- After checking all possible splits of `k` for the current point `(x1, y1)`, add it to the `pointCounts` map. Create a key for `(x1, y1)` and increment its frequency in the map.
- Return `count` after iterating through all points.

# Solutions
### Java

```java
class Solution {
public
  int countPairs(List<List<Integer>> coordinates, int k) {
    Map<List<Integer>, Integer> cnt = new HashMap<>();
    int ans = 0;
    for (var c : coordinates) {
      int x2 = c.get(0), y2 = c.get(1);
      for (int a = 0; a <= k; ++a) {
        int b = k - a;
        int x1 = a ^ x2, y1 = b ^ y2;
        ans += cnt.getOrDefault(List.of(x1, y1), 0);
      }
      cnt.merge(c, 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPairs(vector<vector<int>> &coordinates, int k) {
    map<pair<int, int>, int> cnt;
    int ans = 0;
    for (auto &c : coordinates) {
      int x2 = c[0], y2 = c[1];
      for (int a = 0; a <= k; ++a) {
        int b = k - a;
        int x1 = a ^ x2, y1 = b ^ y2;
        ans += cnt[{x1, y1}];
      }
      ++cnt[{x2, y2}];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int: cnt = Counter() ans = 0 for x2, y2 in coordinates: for a in range(k + 1): b = k - a x1, y1 = a ^ x2, b ^ y2 ans += cnt[(x1, y1)] cnt[(x2, y2)] += 1 return ans

```