Jobs

Interviews

Discussions

Count Pairs of Points With Distance k

#867 Most AskedMedium

Count Pairs of Points With Distance k #867 Most Asked

Medium

Google

22 views

Topics:

Bit Manipulation

You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [x_i, y_i] are the coordinates of the i^th point in a 2D plane.

We define the distance between two points (x₁, y₁) and (x₂, y₂) 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 <= x_i, y_i <= 10⁶
0 <= k <= 100

Try coding it in LeetCode

Count Pairs of Points With Distance k

#867 Most AskedMedium

Count Pairs of Points With Distance k #867 Most Asked

Medium

Google

22 views

Topics:

Bit Manipulation

You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [x_i, y_i] are the coordinates of the i^th point in a 2D plane.

We define the distance between two points (x₁, y₁) and (x₂, y₂) 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 <= x_i, y_i <= 10⁶
0 <= k <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type and range of values for the x and y coordinates of the points? Are they integers, and if so, what are the minimum and maximum possible values?
Is `k` an integer? Can `k` be negative or zero?
If no pairs of points exist with a distance of `k`, what should I return?
Can there be duplicate points in the input? If so, should I count pairs of duplicate points that are distance `k` apart?
How large can the input array of points be? Is there a specific constraint that might cause integer overflow if I naively compute distances?

Brute Force Solution

Approach

We need to find pairs of points that are exactly a certain distance apart. The brute force method is like checking every possible pair of points and seeing if their distance matches what we are looking for. It's straightforward: compare each point with every other point.

Here's how the algorithm would work step-by-step:

Take the first point.
Compare its distance to the second point. Is it the distance we're looking for? If so, count it.
Compare the first point's distance to the third point. Is it the distance we're looking for? If so, count it.
Continue comparing the first point to every other point in the collection.
Now, take the second point.
Compare the second point's distance to the third point. (We already compared it to the first point, so we can skip that). Is it the distance we're looking for? If so, count it.
Continue comparing the second point to every point after it.
Repeat this process, taking each point in turn and comparing it to all the points that come after it in the collection.
The final count is the total number of pairs that are exactly the specified distance apart.

Code Implementation

def count_pairs_brute_force(points, target_distance):
    pair_count = 0
    number_of_points = len(points)

    for first_point_index in range(number_of_points):
        # We iterate through all possible first points

        for second_point_index in range(first_point_index + 1, number_of_points):
            # Avoid double counting by comparing to points after

            point_one = points[first_point_index]
            point_two = points[second_point_index]

            distance = ((point_one[0] - point_two[0]) ** 2 + \
                        (point_one[1] - point_two[1]) ** 2) ** 0.5

            if distance == target_distance:
                # Check if the distance equals target

                pair_count += 1

    return pair_count

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each of the n points in the input. For each point, it calculates the distance to every other point that comes after it in the list. In the worst-case scenario, where no optimization exists to avoid distance calculations, this results in roughly (n-1) comparisons for the first point, (n-2) for the second, and so on. Therefore, the total number of operations is proportional to n * (n-1) / 2 which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm iterates through pairs of points and computes their distance, without creating any auxiliary data structures that scale with the input size. It only uses a few constant space variables, such as loop counters and a variable to store the count of pairs. Therefore, the space required does not depend on the number of points, N. The space complexity is O(1).

Optimal Solution

Approach

The straightforward way to find pairs of points at a certain distance checks every possible pair. A faster approach is to use a tool that organizes the data so we only look at possible pairs that are near each other, saving lots of time.

Here's how the algorithm would work step-by-step:

Create a way to quickly look up points by their location, like organizing them in a grid or table.
For each point, only check other points that are close enough to potentially be the right distance away. Use the organized data structure to find these nearby points efficiently.
Calculate the distance between the original point and each of the nearby points.
If the distance is the desired distance, increase the count of matching pairs.
Repeat this process for every point, making sure not to double count pairs.

Code Implementation

def count_pairs_of_points_with_distance_k(points, target_distance):
    point_map = {}
    pair_count = 0

    for x, y in points:
        if (x, y) not in point_map:
            point_map[(x, y)] = 0
        point_map[(x, y)] += 1

    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            point_one_x, point_one_y = points[i]
            point_two_x, point_two_y = points[j]
            distance = ((point_one_x - point_two_x) ** 2 + (point_one_y - point_two_y) ** 2) ** 0.5

            # Only increment if the calculated distance
            # matches the target distance
            if distance == target_distance:
                pair_count += 1

    # Avoid double counting the pairs.
    return pair_count

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each of the n points. For each point, it uses the organized data structure (e.g., a grid or hash table) to identify nearby points. In the worst-case scenario, where all points are clustered together, checking nearby points for each of the n points could potentially involve comparing each point with every other point. This comparison leads to approximately n * (n-1) distance calculations, which simplifies to O(n^2) in terms of time complexity. Therefore, the overall time complexity is determined by the potential need to compare all possible pairs of points.

Space Complexity

O(N) – The solution uses a data structure, such as a grid or hash map, to organize the points for efficient lookup. In the worst case, this data structure needs to store information about all N points, where N is the number of points given as input. This results in an auxiliary space complexity that is directly proportional to the number of points. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input list of points	Return 0 since no pairs can be formed.
List with only one point	Return 0 since a pair requires at least two points.
All points are the same (duplicates)	The algorithm should count all possible pairs correctly which would be n * (n-1) / 2 if all points have the required distance.
k = 0 (distance is zero)	Only points with identical coordinates will be counted.
Large input size (performance considerations)	Use an efficient algorithm (e.g., using a hash map) to avoid O(n^2) complexity.
Negative coordinates	The algorithm should work correctly with negative coordinates as it only considers the distance between them.
Integer overflow in distance calculation	Use a larger data type (e.g., long) for distance calculations to prevent overflow or use a different algorithm that avoids directly calculating the squared distance.
No pairs with the specified distance k exist	The algorithm should return 0 if no such pairs are found.

Empty input list of points

How to Handle:

Return 0 since no pairs can be formed.

List with only one point

How to Handle:

Return 0 since a pair requires at least two points.

All points are the same (duplicates)

How to Handle:

The algorithm should count all possible pairs correctly which would be n * (n-1) / 2 if all points have the required distance.

k = 0 (distance is zero)

How to Handle:

Only points with identical coordinates will be counted.

Large input size (performance considerations)

How to Handle:

Use an efficient algorithm (e.g., using a hash map) to avoid O(n^2) complexity.

Negative coordinates

How to Handle:

The algorithm should work correctly with negative coordinates as it only considers the distance between them.

Integer overflow in distance calculation

How to Handle:

Use a larger data type (e.g., long) for distance calculations to prevent overflow or use a different algorithm that avoids directly calculating the squared distance.

No pairs with the specified distance k exist

How to Handle:

The algorithm should return 0 if no such pairs are found.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type and range of values for the x and y coordinates of the points? Are they integers, and if so, what are the minimum and maximum possible values?
Is `k` an integer? Can `k` be negative or zero?
If no pairs of points exist with a distance of `k`, what should I return?
Can there be duplicate points in the input? If so, should I count pairs of duplicate points that are distance `k` apart?
How large can the input array of points be? Is there a specific constraint that might cause integer overflow if I naively compute distances?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first point.
Compare its distance to the second point. Is it the distance we're looking for? If so, count it.
Compare the first point's distance to the third point. Is it the distance we're looking for? If so, count it.
Continue comparing the first point to every other point in the collection.
Now, take the second point.
Compare the second point's distance to the third point. (We already compared it to the first point, so we can skip that). Is it the distance we're looking for? If so, count it.
Continue comparing the second point to every point after it.
Repeat this process, taking each point in turn and comparing it to all the points that come after it in the collection.
The final count is the total number of pairs that are exactly the specified distance apart.

Code Implementation

def count_pairs_brute_force(points, target_distance):
    pair_count = 0
    number_of_points = len(points)

    for first_point_index in range(number_of_points):
        # We iterate through all possible first points

        for second_point_index in range(first_point_index + 1, number_of_points):
            # Avoid double counting by comparing to points after

            point_one = points[first_point_index]
            point_two = points[second_point_index]

            distance = ((point_one[0] - point_two[0]) ** 2 + \
                        (point_one[1] - point_two[1]) ** 2) ** 0.5

            if distance == target_distance:
                # Check if the distance equals target

                pair_count += 1

    return pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create a way to quickly look up points by their location, like organizing them in a grid or table.
For each point, only check other points that are close enough to potentially be the right distance away. Use the organized data structure to find these nearby points efficiently.
Calculate the distance between the original point and each of the nearby points.
If the distance is the desired distance, increase the count of matching pairs.
Repeat this process for every point, making sure not to double count pairs.

Code Implementation

def count_pairs_of_points_with_distance_k(points, target_distance):
    point_map = {}
    pair_count = 0

    for x, y in points:
        if (x, y) not in point_map:
            point_map[(x, y)] = 0
        point_map[(x, y)] += 1

    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            point_one_x, point_one_y = points[i]
            point_two_x, point_two_y = points[j]
            distance = ((point_one_x - point_two_x) ** 2 + (point_one_y - point_two_y) ** 2) ** 0.5

            # Only increment if the calculated distance
            # matches the target distance
            if distance == target_distance:
                pair_count += 1

    # Avoid double counting the pairs.
    return pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input list of points	Return 0 since no pairs can be formed.
List with only one point	Return 0 since a pair requires at least two points.
All points are the same (duplicates)	The algorithm should count all possible pairs correctly which would be n * (n-1) / 2 if all points have the required distance.
k = 0 (distance is zero)	Only points with identical coordinates will be counted.
Large input size (performance considerations)	Use an efficient algorithm (e.g., using a hash map) to avoid O(n^2) complexity.
Negative coordinates	The algorithm should work correctly with negative coordinates as it only considers the distance between them.
Integer overflow in distance calculation	Use a larger data type (e.g., long) for distance calculations to prevent overflow or use a different algorithm that avoids directly calculating the squared distance.
No pairs with the specified distance k exist	The algorithm should return 0 if no such pairs are found.

Empty input list of points

How to Handle:

Return 0 since no pairs can be formed.

List with only one point

How to Handle:

Return 0 since a pair requires at least two points.

All points are the same (duplicates)

How to Handle:

The algorithm should count all possible pairs correctly which would be n * (n-1) / 2 if all points have the required distance.

k = 0 (distance is zero)

How to Handle:

Only points with identical coordinates will be counted.

Large input size (performance considerations)

How to Handle:

Use an efficient algorithm (e.g., using a hash map) to avoid O(n^2) complexity.

Negative coordinates

How to Handle:

The algorithm should work correctly with negative coordinates as it only considers the distance between them.

Integer overflow in distance calculation

How to Handle:

Use a larger data type (e.g., long) for distance calculations to prevent overflow or use a different algorithm that avoids directly calculating the squared distance.

No pairs with the specified distance k exist

How to Handle:

The algorithm should return 0 if no such pairs are found.

0/1916 Google questions completed

0/1916 completed