Skip to content

2857. Count Pairs of Points With Distance k 👍

  • Time: $O(kn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int countPairs(vector<vector<int>>& coordinates, int k) {
    int ans = 0;

    for (int x = 0; x <= k; ++x) {
      const int y = k - x;
      unordered_map<pair<int, int>, int, PairHash> count;
      for (const vector<int>& point : coordinates) {
        const int xi = point[0];
        const int yi = point[1];
        if (const auto it = count.find({xi ^ x, yi ^ y}); it != count.cend())
          ans += it->second;
        ++count[{xi, yi}];
      }
    }

    return ans;
  }

 private:
  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int countPairs(List<List<Integer>> coordinates, int k) {
    int ans = 0;

    for (int x = 0; x <= k; ++x) {
      final int y = k - x;
      Map<Pair<Integer, Integer>, Integer> count = new HashMap<>();
      for (List<Integer> point : coordinates) {
        final int xi = point.get(0);
        final int yi = point.get(1);
        ans += count.getOrDefault(new Pair<>(xi ^ x, yi ^ y), 0);
        count.merge(new Pair<>(xi, yi), 1, Integer::sum);
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def countPairs(self, coordinates: list[list[int]], k: int) -> int:
    ans = 0

    for x in range(k + 1):
      y = k - x
      count = collections.Counter()
      for xi, yi in coordinates:
        ans += count[(xi ^ x, yi ^ y)]
        count[(xi, yi)] += 1

    return ans