Count Pairs of Points With Distance k - Practice Coding Problems

Count Pairs of Points With Distance k - Problem

You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: coordinates = [[1,2],[3,2],[1,3],[3,3]], k = 1

› Output: 2

💡 Note: Distance between [1,2] and [1,3]: (1⊕1)+(2⊕3) = 0+1 = 1. Distance between [3,2] and [3,3]: (3⊕3)+(2⊕3) = 0+1 = 1. Total pairs = 2.

Example 2 — No Pairs

$ Input: coordinates = [[1,3],[1,3],[1,3],[1,4],[1,4],[1,4],[1,4]], k = 2

› Output: 0

💡 Note: Distance between any [1,3] and [1,4]: (1⊕1)+(3⊕4) = 0+7 = 7 ≠ 2. Distance between same coordinates is 0 ≠ 2. No pairs found.

Example 3 — All Same Points

$ Input: coordinates = [[1,1],[1,1],[1,1]], k = 0

› Output: 3

💡 Note: Distance between any two identical points: (1⊕1)+(1⊕1) = 0+0 = 0 = k. We have 3 choose 2 = 3 pairs: (0,1), (0,2), (1,2).

Constraints

2 ≤ coordinates.length ≤ 10⁴
0 ≤ coordinates[i][0], coordinates[i][1] ≤ 10⁶
0 ≤ k ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

2D coordinates array and target distance k

XOR Distance

Calculate (x1⊕x2) + (y1⊕y2) for each pair

Count Matches

Count pairs where distance equals k

Key Takeaway

🎯 Key Insight: XOR distance enables efficient complement lookup using hash maps, reducing time complexity from O(n²) to O(n×k)

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that XOR distance allows us to calculate complementary coordinates efficiently. The hash map approach stores all coordinates and checks for complements in O(n×k) time instead of O(n²). Time: O(n×k), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n × k)	O(n)	Use hash map to store coordinates and check for complementary points
Brute Force	O(n²)	O(1)	Check every pair of points to see if their XOR distance equals k

Hash Map Optimization — Algorithm Steps

Store all coordinates in a hash map with their counts
For each point, iterate through possible dx values from 0 to k
Calculate dy = k - dx and check if (x⊕dx, y⊕dy) exists
Count valid pairs avoiding double counting

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Map

Store all coordinates with frequencies

Check Complements

For each point, try all possible dx values

Count Pairs

Look up complementary points in O(1) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COORDS 1000
#define MAX_KEY_LEN 50

struct HashEntry {
    char key[MAX_KEY_LEN];
    int count;
    struct HashEntry* next;
};

struct HashEntry* hashTable[MAX_COORDS];

unsigned int hash(const char* key) {
    unsigned int hash = 0;
    while (*key) {
        hash = hash * 31 + *key++;
    }
    return hash % MAX_COORDS;
}

void put(const char* key, int value) {
    unsigned int index = hash(key);
    struct HashEntry* entry = hashTable[index];
    
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            entry->count += value;
            return;
        }
        entry = entry->next;
    }
    
    entry = malloc(sizeof(struct HashEntry));
    strcpy(entry->key, key);
    entry->count = value;
    entry->next = hashTable[index];
    hashTable[index] = entry;
}

int get(const char* key) {
    unsigned int index = hash(key);
    struct HashEntry* entry = hashTable[index];
    
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            return entry->count;
        }
        entry = entry->next;
    }
    return 0;
}

int solution(int coordinates[][2], int n, int k) {
    int count = 0;
    
    // Initialize hash table
    for (int i = 0; i < MAX_COORDS; i++) {
        hashTable[i] = NULL;
    }
    
    // Store coordinates
    for (int i = 0; i < n; i++) {
        char key[MAX_KEY_LEN];
        sprintf(key, "%d,%d", coordinates[i][0], coordinates[i][1]);
        put(key, 1);
    }
    
    // Find pairs
    for (int i = 0; i < n; i++) {
        int x = coordinates[i][0], y = coordinates[i][1];
        for (int dx = 0; dx <= k; dx++) {
            int dy = k - dx;
            int targetX = x ^ dx;
            int targetY = y ^ dy;
            char targetKey[MAX_KEY_LEN];
            sprintf(targetKey, "%d,%d", targetX, targetY);
            
            int freq = get(targetKey);
            if (freq > 0) {
                if (targetX == x && targetY == y) {
                    count += freq - 1;
                } else if (targetX > x || (targetX == x && targetY > y)) {
                    count += freq;
                }
            }
        }
    }
    
    return count / 2;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int coordinates[1000][2];
    int n = 0;
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            coordinates[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            coordinates[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        }
        ptr++;
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(coordinates, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

For each of n points, we check k+1 possible dx values

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n coordinate pairs

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~25 min Avg. Time

486 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler