2857. Count Pairs of Points With Distance k
Problem Description
In this problem, we are given a list of points on a 2D plane, where each point is represented as a pair of integers (x, y). These pairs are the coordinates of the points. We are also given an integer k
. The task is to count how many unique pairs of points (i, j)
have a specific distance between them, where the distance is defined as (x1 XOR x2) + (y1 XOR y2)
and XOR
stands for the bitwise XOR operation. A key point to note is that a valid pair (i, j)
must have the indices i
less than j
to ensure pairs are not counted multiple times and to maintain uniqueness.
Intuition
The intuition behind the solution emerges from understanding how XOR operation works and then optimizing the brute force approach of checking each possible pair of points to see if they meet our distance criteria.
Here are the steps to understand and arrive at the solution:
-
Understanding XOR: The XOR operation has a crucial property: if
a XOR b = c
, thena = b XOR c
andb = a XOR c
. This property will help us quickly find potential pairs that can have the distancek
between them. -
Iterating Efficiently: A naive approach would involve checking every possible pair of points, which would be inefficient with large datasets. We can optimize this by smartly iterating over possible values of one coordinate, reducing the search space.
-
Counter Dictionary: We use a Counter (dictionary subclass in Python that helps keep track of element counts) to keep track of how many points with certain coordinates we already have seen. The key of the counter will be the coordinate pair, and the value is the number of times we have seen that specific pair.
-
Calculating Potential Matches: For each new point
(x2, y2)
we're inspecting, we iterate through possible values ofa
(from0
tok
) and calculate a correspondingb
such thata + b = k
. With these values ofa
andb
, we can determine what the coordinate(x1, y1)
of a potential matching point would need to be using the XOR property mentioned earlier. -
Counting Valid Pairs: For each of these potential matching coordinates
(x1, y1)
, we use our counter to see if we have previously come across such a point. If we have, we know that the current point(x2, y2)
and the counted(x1, y1)
would form a valid pair, so we add the count from the counter to our answer. -
Updating the Counter: After running through all possible
a
and correspondingb
, we add the current point(x2, y2)
to our counter, indicating that we have now seen this particular point. -
Return the Answer: Once we have iterated over all points and calculated the valid pairs, we return the total count.
Through this method, we can efficiently and systematically count all the pairs that have the XOR-based distance of k
, without having to evaluate each pair of points individually.
Solution Approach
The solution uses a blend of counting methodology with smart iteration based on the properties of the XOR operation to count the number of valid point pairs that are at a distance k
from each other.
Here is a step-by-step explanation of the algorithm:
-
Initialization:
- A
Counter
objectcnt
is initialized to keep track of how many times a particular point(x, y)
is seen. In Python, aCounter
is a dictionary that stores elements as keys and their counts as values. - An integer
ans
is initialized to0
, which will accumulate the number of valid pairs that meet the distance criteria.
- A
-
Iterate Over Points:
- We iterate over each point
(x2, y2)
in thecoordinates
array using a for-loop. This loop is responsible for looking at each point and determining how many points we've seen so far can form a valid pair with it at distancek
.
- We iterate over each point
-
Determining Potential Pairs Based on Distance
k
:- Inside the first loop, another for-loop runs through integer values from
0
tok
inclusive. With each iteration, we takea
as the current value of the loop, and we computeb
such thatb = k - a
. - We then use the
XOR
property to find whatx1
andy1
would be ifx2 XOR x1 = a
andy2 XOR y1 = b
. This gives us the coordinates of a point that could be at the required distancek
from(x2, y2)
.
- Inside the first loop, another for-loop runs through integer values from
-
Counting and Summing Valid Pairs:
- Using the calculated
(x1, y1)
, we check thecnt
dictionary to see if we already came across this point in our previous iterations. If so, the value from the dictionary for the key(x1, y1)
is added toans
. This step counts how many times we have a point that can pair with our current point to create a distance ofk
.
- Using the calculated
-
Updating the Counter:
- After inspecting all possible matching points for
(x2, y2)
, we update thecnt
dictionary by incrementing the count of the current point(x2, y2)
. This means that now(x2, y2)
can be considered as a potential match for future points.
- After inspecting all possible matching points for
-
Returning the Result:
- Once all points have been accounted for, and all valid pairs have been counted, the final value of
ans
, which represents the number of valid pairs with the specified distance, is returned.
- Once all points have been accounted for, and all valid pairs have been counted, the final value of
The algorithm efficiently uses a single pass through the points while leveraging the constant-time lookup feature of dictionaries in Python to keep the overall performance manageable. Moreover, the approach takes full advantage of the XOR operationās properties, avoiding an exhaustive enumeration of all possible point pairs, which could otherwise become computationally expensive.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example with the following points and k = 5
:
points = [(0, 0), (1, 4), (4, 1), (5, 0)]
Now, let's walk through the solution approach step by step for k = 5
:
-
Initialization:
cnt = Counter()
is initialized to keep track of how many times a particular point is seen.ans = 0
is initialized to accumulate the number of valid pairs.
-
Iterate Over Points:
- First we consider the point
(0, 0)
. There are no previous points to compare it with, so we simply move on after adding it to thecnt
.
- First we consider the point
-
Determining Potential Pairs Based on Distance
k
:- Examining the next point
(1, 4)
. We iterate fora
from0
to5
(ourk
value).- When
a = 0
: Thenb = 5
, we look for a point with coordinates such that0 XOR x1 = 0
and4 XOR y1 = 5
. This gives usx1 = 0
andy1 = 1
. But we have not seen(0, 1)
before, so there is no match. - When
a = 1
: Thenb = 4
, we seek a point where1 XOR x1 = 1
and4 XOR y1 = 4
. We getx1 = 0
andy1 = 0
which we have seen, so we add1
toans
. - We continue this process for other values of
a
until5
but find no more matches.
- When
cnt[(1,4)] += 1
- Examining the next point
-
Next Points:
- For
(4, 1)
, repeating the process for values ofa
:- When
a = 0
: Thenb = 5
, and we look for4 XOR x1 = 0
&1 XOR y1 = 5
which yieldsx1 = 4
,y1 = 4
. No such point exists yet. - When
a = 1
: Thenb = 4
, and4 XOR x1 = 1
&1 XOR y1 = 4
which yieldsx1 = 5
,y1 = 5
. No match. - And so on, until a match is found for
a = 4
: Thenb = 1
. Here,x1 = 0
&y1 = 0
is a match, so we add1
toans
.
- When
cnt[(4, 1)] += 1
- For
-
Last Point:
- For
(5, 0)
, following the same method for different values ofa
, we find a match fora = 1
&b = 4
, which corresponds to the point(4, 4)
. It's not incnt
, so no match is added toans
. cnt[(5, 0)] += 1
- For
-
Returning the Result:
- Having processed all points, we find that
ans = 2
. There are two unique pairs of points with XOR-based distance5
:(0, 0) & (1, 4)
,(0, 0) & (4, 1)
.
- Having processed all points, we find that
The algorithm allowed us to figure out the number of valid point pairs with the desired property by efficiently iterating through the list of points and using the Counter to avoid unnecessary pair checks.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def count_pairs(self, coordinates: List[List[int]], k: int) -> int:
5 # Create a counter to keep track of the number of occurrences of each coordinate
6 count = Counter()
7 # Initialize the answer to zero
8 ans = 0
9
10 # Iterate over all coordinates
11 for x2, y2 in coordinates:
12 # Check all possible combinations of (a, b) where a + b = k
13 for a in range(k + 1):
14 b = k - a
15
16 # Calculate the original coordinates (x1, y1) before being XOR'ed
17 # by using the current coordinate (x2, y2) and the calculated values of a and b
18 x1, y1 = a ^ x2, b ^ y2
19
20 # Add the number of times the original coordinate (x1, y1) has been seen so far
21 ans += count[(x1, y1)]
22
23 # Increment the count of the current coordinate (x2, y2)
24 count[(x2, y2)] += 1
25
26 # Return the total count of pairs found
27 return ans
28
1import java.util.*;
2
3class Solution {
4
5 // Method to count the number of pairs whose bitwise XOR meets specified conditions
6 public int countPairs(List<List<Integer>> coordinates, int k) {
7 // Create a hashmap to store the frequency of occurrences of each coordinate pair
8 Map<List<Integer>, Integer> frequencyCount = new HashMap<>();
9 int answer = 0; // Initialize count of valid pairs to 0
10
11 // Iterating through each coordinate pair in the list
12 for (List<Integer> coordinate : coordinates) {
13 // Extract x2 and y2 from the current coordinate
14 int x2 = coordinate.get(0);
15 int y2 = coordinate.get(1);
16
17 // Calculate all possible pairs (x1, y1) within the range 0 to k
18 for (int a = 0; a <= k; ++a) {
19 int b = k - a; // Since a + b should be equal to k
20
21 // Compute x1 and y1 using XOR operation on a, b with x2, y2 respectively
22 int x1 = a ^ x2;
23 int y1 = b ^ y2;
24
25 // Increment count for this pair if it's already in the hashmap
26 answer += frequencyCount.getOrDefault(List.of(x1, y1), 0);
27 }
28
29 // Update the frequencyMap with the current coordinate,
30 // incrementing its count or adding it if doesn't exist
31 frequencyCount.merge(coordinate, 1, Integer::sum);
32 }
33
34 // Return the final count of valid pairs
35 return answer;
36 }
37}
38
1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6 // Method to count the number of distinct pairs of points from the input coordinates that have a Manhattan distance of exactly k.
7 int countPairs(vector<vector<int>>& coordinates, int k) {
8 // Create a hash map to count occurrences of points
9 unordered_map<long long, int> pointCount;
10
11 // Helper function to convert a 2D point into a unique long long value
12 auto getUniqueKey = [](int x, int y) -> long long {
13 return static_cast<long long>(x) * 1000000L + y;
14 };
15
16 int pairCount = 0; // Initialize the count of pairs to zero
17
18 // Iterate through each point in coordinates
19 for (auto& point : coordinates) {
20 int x2 = point[0], y2 = point[1];
21
22 // Check all possible points (x1, y1) that could form a pair with (x2, y2) having Manhattan distance k
23 for (int a = 0; a <= k; ++a) {
24 int b = k - a;
25 // Use the XOR operation to find the corresponding x1 and y1
26 int x1 = a ^ x2;
27 int y1 = b ^ y2;
28
29 // Increase the count of pairs by the occurrences of the (x1, y1) point
30 pairCount += pointCount[getUniqueKey(x1, y1)];
31 }
32 // Register the occurrence of the current point (x2, y2)
33 ++pointCount[getUniqueKey(x2, y2)];
34 }
35
36 // Return the total count of pairs found
37 return pairCount;
38 }
39};
40
1function countPairs(coordinates: number[][], k: number): number {
2 // Initialize a map to keep track of the count of each coordinate pair
3 const countMap: Map<number, number> = new Map();
4
5 // Define a helper function to create a unique hash for a pair of coordinates
6 const hashCoordinates = (x: number, y: number): number => x * 1000000 + y;
7
8 // Initialize the count of valid pairs
9 let pairCount = 0;
10
11 // Loop through each coordinate in the array
12 for (const [coordinateX2, coordinateY2] of coordinates) {
13 // Check all possible pairs with Manhattan distance = k
14 for (let a = 0; a <= k; ++a) {
15 const b = k - a;
16 // Find the counterpart for the current coordinate that will form a valid pair
17 const partnerX = a ^ coordinateX2;
18 const partnerY = b ^ coordinateY2;
19 // Increase the count by the number of times the counterpart has been seen
20 pairCount += countMap.get(hashCoordinates(partnerX, partnerY)) ?? 0; // Nullish coalescing to handle undefined values
21 }
22 // Increment the count for the current coordinate pair in the map
23 const currentHash = hashCoordinates(coordinateX2, coordinateY2);
24 countMap.set(currentHash, (countMap.get(currentHash) ?? 0) + 1);
25 }
26
27 // Return the final count of valid pairs
28 return pairCount;
29}
30
Time and Space Complexity
Time Complexity
The given Python code has a nested loop where the outer loop goes through each coordinate in the list coordinates
, and for each of these coordinates, the inner loop iterates k + 1
times. If n
is the number of coordinates, the total number of iterations of the inner loop across all executions of the outer loop is n * (k + 1)
. Since the other operations inside the inner loop, including dictionary access and updates, take constant time, the time complexity is O(n * k)
.
Space Complexity
The space complexity of the code is determined by the additional space required for the Counter
object cnt
. In the worst-case scenario, if all coordinates are unique, the counter will have an entry for each coordinate in the list. Therefore, if there are n
coordinates, the space complexity will be O(n)
for storing all the unique coordinates in cnt
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!