Count Pairs of Points With Distance k

Med

#2554Time: 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.

Patterns

Bit Manipulation

Data structures

Array Hash Table

Prompt

You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [x_i, y_i] are the coordinates of the i^th point in a 2D plane.

We define the distance between two points (x₁, y₁) and (x₂, y₂) 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 <= x_i, y_i <= 10⁶
0 <= k <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int countPairs(int[][] coordinates, int k) {3        int n = coordinates.length;4        int count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                int x1 = coordinates[i][0];8                int y1 = coordinates[i][1];9                int x2 = coordinates[j][0];10                int y2 = coordinates[j][1];11                12                if ((x1 ^ x2) + (y1 ^ y2) == k) {13                    count++;14                }15            }16        }17        return count;18    }19}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int countPairs(int[][] coordinates, int k) {6        // Map to store frequency of points. Key is a packed long, value is count.7        Map<Long, Integer> pointCounts = new HashMap<>();8        int count = 0;9        10        for (int[] p : coordinates) {11            int x1 = p[0];12            int y1 = p[1];13            14            // Iterate through all possible values for the x-component of the distance.15            for (int i = 0; i <= k; i++) {16                int x_xor_val = i;17                int y_xor_val = k - i;18                19                // Calculate the coordinates of the target point (x2, y2).20                int x2 = x1 ^ x_xor_val;21                int y2 = y1 ^ y_xor_val;22                23                // Pack (x2, y2) into a long to use as a map key.24                // x, y <= 10^6, which is < 2^20. Shifting by 21 is safe.25                long key = ((long)x2 << 21) | y2;26                27                // Add the number of times we've seen this target point.28                count += pointCounts.getOrDefault(key, 0);29            }30            31            // Add the current point to the map for subsequent checks.32            long currentKey = ((long)x1 << 21) | y1;33            pointCounts.put(currentKey, pointCounts.getOrDefault(currentKey, 0) + 1);34        }35        36        return count;37    }38}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int countPairs(List<List<Integer>> coordinates, int k) {4    Map<List<Integer>, Integer> cnt = new HashMap<>();5    int ans = 0;6    for (var c : coordinates) {7      int x2 = c.get(0), y2 = c.get(1);8      for (int a = 0; a <= k; ++a) {9        int b = k - a;10        int x1 = a ^ x2, y1 = b ^ y2;11        ans += cnt.getOrDefault(List.of(x1, y1), 0);12      }13      cnt.merge(c, 1, Integer : : sum);14    }15    return ans;16  }17}

1class Solution {2public:3  int countPairs(vector<vector<int>> &coordinates, int k) {4    map<pair<int, int>, int> cnt;5    int ans = 0;6    for (auto &c : coordinates) {7      int x2 = c[0], y2 = c[1];8      for (int a = 0; a <= k; ++a) {9        int b = k - a;10        int x1 = a ^ x2, y1 = b ^ y2;11        ans += cnt[{x1, y1}];12      }13      ++cnt[{x2, y2}];14    }15    return ans;16  }17};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem