We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Pairs of Points With Distance k

Difficulty: Medium

Problem Description

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). Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.

Key Insights

  • The distance metric is defined using the XOR operation, which will yield results based on the differing bits of the coordinates.
  • The problem can be approached using a hash map to count occurrences of coordinate pairs.
  • Since k is limited to a small range (0 to 100), we can efficiently track pairs of points that yield the same distance.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of points and m is the number of bits in the coordinates (up to 20 bits for values up to 10^6).
Space Complexity: O(n), for storing points in a hash map.

Solution

To solve this problem, we can iterate through each point and calculate the desired distance for every other point using the XOR operation. We can store the counts of already encountered points in a hash map. For each new point, we can check how many previous points have the required XOR distance that equals k.

Code Solutions

def countPairs(coordinates, k):
    from collections import defaultdict
    
    count = 0
    freq = defaultdict(int)
    
    for (x, y) in coordinates:
        # Check for all possible previous points
        for dx in range(101):  # k can be at most 100
            for dy in range(101):
                target_x = x ^ dx
                target_y = y ^ dy
                if (target_x, target_y) in freq:
                    count += freq[(target_x, target_y)]
        
        freq[(x, y)] += 1  # Add the current point to frequency map
    
    return count
← Back to All Questions