LeetCode 2857. Count Pairs of Points With Distance k Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Example 1:

Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output: 2
Explanation: We can choose the following pairs:
- (0,1): Because we have (1 XOR 4) + (2 XOR 2) = 5.
- (2,3): Because we have (1 XOR 5) + (3 XOR 2) = 5.

Example 2:

Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.

 

Constraints:

• 2 <= coordinates.length <= 50000
• 0 <= xi, yi <= 106
• 0 <= k <= 100

Solutions

Solution 1: Hash Table + Enumeration

We can use a hash table cnt to count the occurrence of each point in the array coordinates.

Next, we enumerate each point (x₂, y₂) in the array coordinates. Since the range of k is [0, 100], and the result of x₁ \oplus x₂ or y₁ \oplus y₂ is always greater than or equal to 0, we can enumerate the result a of x₁ \oplus x₂ in the range [0,..k]. Then, the result of y₁ \oplus y₂ is b = k - a. In this way, we can calculate the values of x₁ and y₁, and add the occurrence of (x₁, y₁) to the answer.

The time complexity is O(n × k), and the space complexity is O(n). Here, n is the length of the array coordinates.

PythonJavaC++GoTypeScript

class Solution: def countPairs(self, coordinates: List[List[int]], k: int) -> int: cnt = Counter() ans = 0 for x2, y2 in coordinates: for a in range(k + 1): b = k - a x1, y1 = a ^ x2, b ^ y2 ans += cnt[(x1, y1)] cnt[(x2, y2)] += 1 return ans(code-box)

class Solution { public int countPairs(List<List<Integer>> coordinates, int k) { Map<List<Integer>, Integer> cnt = new HashMap<>(); int ans = 0; for (var c : coordinates) { int x2 = c.get(0), y2 = c.get(1); for (int a = 0; a <= k; ++a) { int b = k - a; int x1 = a ^ x2, y1 = b ^ y2; ans += cnt.getOrDefault(List.of(x1, y1), 0); } cnt.merge(c, 1, Integer::sum); } return ans; } }(code-box)

class Solution { public: int countPairs(vector<vector<int>>& coordinates, int k) { map<pair<int, int>, int> cnt; int ans = 0; for (auto& c : coordinates) { int x2 = c[0], y2 = c[1]; for (int a = 0; a <= k; ++a) { int b = k - a; int x1 = a ^ x2, y1 = b ^ y2; ans += cnt[{x1, y1}]; } ++cnt[{x2, y2}]; } return ans; } };(code-box)

func countPairs(coordinates [][]int, k int) (ans int) { cnt := map[[2]int]int{} for _, c := range coordinates { x2, y2 := c[0], c[1] for a := 0; a <= k; a++ { b := k - a x1, y1 := a^x2, b^y2 ans += cnt[[2]int{x1, y1}] } cnt[[2]int{x2, y2}]++ } return }(code-box)

function countPairs(coordinates: number[][], k: number): number { const cnt: Map<number, number> = new Map(); const f = (x: number, y: number): number => x * 1000000 + y; let ans = 0; for (const [x2, y2] of coordinates) { for (let a = 0; a <= k; ++a) { const b = k - a; const [x1, y1] = [a ^ x2, b ^ y2]; ans += cnt.get(f(x1, y1)) ?? 0; } cnt.set(f(x2, y2), (cnt.get(f(x2, y2)) ?? 0) + 1); } return ans; }(code-box)