Count Pairs of Points With Distance k

MEDIUM

Description

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

Checkout 2 different approaches to solve Count Pairs of Points With Distance k. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Pairs of Points With Distance k. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count Pairs of Points With Distance k

Patterns:

Bit Manipulation

Data Structures:

ArrayHash Table