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^40 <= xi, yi <= 10^60 <= k <= 100
Hints for Count Pairs of Points With Distance k
Hint 1
Checking all pairs is quadratic. But
kis tiny — at most 100.Hint 2
If the distance is
k, thenx1 XOR x2 = aandy1 XOR y2 = k - afor someain0..k.Hint 3
XOR is invertible: given
(x1, y1)anda, 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
- Keep a hash map
cntfrom point to how many times it has appeared so far. - For each point
(x, y)in order, and eachafrom 0 tok, addcnt[(x XOR a, y XOR (k - a))]to the answer. - Then increment
cnt[(x, y)]. - 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
adeterminesx1 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 = 0a 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 totalJava
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