Count Pairs of Points With Distance k
MedPrompt
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
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
countto 0. - Get the number of points,
n. - Use a nested loop structure. The outer loop runs from
i = 0ton-2. - The inner loop runs from
j = i + 1ton-1. This ensures each pair of points(i, j)is considered exactly once withi < j. - Inside the inner loop, retrieve the coordinates for point
i(x1,y1) and pointj(x2,y2). - Calculate the distance:
dist = (x1 XOR x2) + (y1 XOR y2). - If
distis equal tok, increment thecount. - 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.
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; }}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.
Solutions
Solution
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; }}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.