Count pairs of points with distance k

Array Hash Table Bit Manipulation

32.8% acceptance

Feb 25, 2026

282

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) 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(coordinates: Vec<Vec<i32>>, k: i32) -> i32 {
    use std::collections::HashMap;
    let mut seen: HashMap<(i32, i32), i32> = HashMap::new();
    let mut ans = 0i32;
    for coord in &coordinates {
      let (x, y) = (coord[0], coord[1]);
      for a in 0..=k {
        let b = k - a;
        let nx = x ^ a;
        let ny = y ^ b;
        ans += seen.get(&(nx, ny)).cloned().unwrap_or(0);
      }
      *seen.entry((x, y)).or_insert(0) += 1;
    }
    ans
  }
}