Count Pairs of Points With Distance k

Medium
1807.

Count Pairs of Points With Distance k

Count Pairs of Points With Distance k is a medium coding problem on arrays, hash table and bit manipulation, asked in Google interviews.

You are given a 2D integer array coordinates, where coordinates[i] = [xi, yi] is a point in the plane, and an integer k.

Define the distance between points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2), where XOR is the bitwise exclusive-or.

Return the number of pairs (i, j) with i < j whose distance is exactly k.

Example 1

Input
coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output
2
Explanation
`(1,2)`–`(4,2)` gives `5 + 0` and `(1,3)`–`(5,2)` gives `4 + 1`.

Example 2

Input
coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output
10
Explanation
Every one of the 10 pairs of identical points is at distance 0.

Example 3

Input
coordinates = [[0,0],[3,5]], k = 8
Output
1

Constraints

  • 2 <= coordinates.length <= 5 * 10^4
  • 0 <= xi, yi <= 10^6
  • 0 <= k <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} coordinates
 * @param {number} k
 * @return {number}
 */
var countPairs = function(coordinates, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Pairs of Points With Distance k — Problem & Solution

Count Pairs of Points With Distance k solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Pairs of Points With Distance k is a medium coding problem on arrays, hash table and bit manipulation, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Bit Manipulation
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a 2D integer array coordinates, where coordinates[i] = [xi, yi] is a point in the plane, and an integer k.

Define the distance between points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2), where XOR is the bitwise exclusive-or.

Return the number of pairs (i, j) with i < j whose distance is exactly k.

Example 1

Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output: 2
Explanation: `(1,2)`–`(4,2)` gives `5 + 0` and `(1,3)`–`(5,2)` gives `4 + 1`.

Example 2

Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Every one of the 10 pairs of identical points is at distance 0.

Example 3

Input: coordinates = [[0,0],[3,5]], k = 8
Output: 1

Constraints

  • 2 <= coordinates.length <= 5 * 10^4
  • 0 <= xi, yi <= 10^6
  • 0 <= k <= 100

Hints for Count Pairs of Points With Distance k

  1. Hint 1

    Checking all pairs is quadratic. But k is tiny — at most 100.

  2. Hint 2

    If the distance is k, then x1 XOR x2 = a and y1 XOR y2 = k - a for some a in 0..k.

  3. Hint 3

    XOR is invertible: given (x1, y1) and a, the partner must be exactly (x1 XOR a, y1 XOR (k - a)). Look that point up in a hash map of the points seen so far.

How to solve Count Pairs of Points With Distance k

Split k as a + (k - a). For a fixed point and a fixed split, the partner point is fully determined by XOR, so a hash map of earlier points answers each of the k + 1 splits in O(1).

Approach

  1. Keep a hash map cnt from point to how many times it has appeared so far.
  2. For each point (x, y) in order, and each a from 0 to k, add cnt[(x XOR a, y XOR (k - a))] to the answer.
  3. Then increment cnt[(x, y)].
  4. Return the answer.

Why it works

Both XOR terms are non-negative, so a distance of k means x1 XOR x2 = a for exactly one a in 0..k, with y1 XOR y2 = k - a. Since x2 = x1 XOR a and y2 = y1 XOR (k - a), each pair is counted once for its one split, when its later point is processed.

Complexity

  • Time — O(n · k)
  • Space — O(n)

Pitfalls

  • The splits are disjoint because a determines x1 XOR x2; no pair is counted twice.
  • Encode a point as one 64-bit key (x · 2^20 + y) or a pair — coordinates go up to 10^6.
  • Look up before inserting, so with k = 0 a point never pairs with itself.

Reference solution

Python

from typing import List

def countPairs(coordinates: List[List[int]], k: int) -> int:
    cnt = {}
    total = 0
    for x, y in coordinates:
        for a in range(k + 1):
            total += cnt.get((x ^ a, y ^ (k - a)), 0)
        cnt[(x, y)] = cnt.get((x, y), 0) + 1
    return total

Java

public static int countPairs(int[][] coordinates, int k) {
    HashMap<Long, Integer> cnt = new HashMap<>();
    int total = 0;
    for (int[] p : coordinates) {
        int x = p[0], y = p[1];
        for (int a = 0; a <= k; a++) {
            Integer got = cnt.get(((long) (x ^ a) << 20) | (y ^ (k - a)));
            if (got != null) total += got;
        }
        cnt.merge(((long) x << 20) | y, 1, Integer::sum);
    }
    return total;
}

C++

int countPairs(vector<vector<int>>& coordinates, int k) {
    unordered_map<long long, int> cnt;
    int total = 0;
    for (auto& p : coordinates) {
        int x = p[0], y = p[1];
        for (int a = 0; a <= k; a++) {
            auto it = cnt.find(((long long) (x ^ a) << 20) | (y ^ (k - a)));
            if (it != cnt.end()) total += it->second;
        }
        cnt[((long long) x << 20) | y]++;
    }
    return total;
}

JavaScript

var countPairs = function(coordinates, k) {
    var cnt = new Map();
    var total = 0;
    for (var i = 0; i < coordinates.length; i++) {
        var x = coordinates[i][0], y = coordinates[i][1];
        for (var a = 0; a <= k; a++) {
            var got = cnt.get((x ^ a) * 1048576 + (y ^ (k - a)));
            if (got !== undefined) total += got;
        }
        var key = x * 1048576 + y;
        var prev = cnt.get(key);
        cnt.set(key, (prev === undefined ? 0 : prev) + 1);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets