Jobs

Interviews

Discussions

Number of Boomerangs

#1691 Most AskedMedium

Number of Boomerangs #1691 Most Asked

Medium

Google

5 views

Topics:

Arrays

You are given n points in the plane that are all distinct, where points[i] = [x_i, y_i]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Return the number of boomerangs.

Example 1:

Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Example 3:

Input: points = [[1,1]]
Output: 0

Constraints:

n == points.length
1 <= n <= 500
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
All the points are unique.

Try coding it in LeetCode

Number of Boomerangs

#1691 Most AskedMedium

Number of Boomerangs #1691 Most Asked

Medium

Google

5 views

Topics:

Arrays

Return the number of boomerangs.

Example 1:

Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Example 3:

Input: points = [[1,1]]
Output: 0

Constraints:

n == points.length
1 <= n <= 500
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
All the points are unique.

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 expected range of the x and y coordinates? Can they be negative?
What is the size of the input array? Should I be concerned about exceeding memory limits?
If there are no boomerangs, what value should I return? Should I return 0?
Can points overlap (i.e., have identical coordinates)? If so, how should that be handled?
Is the order of points within a boomerang important? For example, is (i, j, k) considered different from (i, k, j)?

Brute Force Solution

Approach

The brute force approach to finding boomerangs involves examining every possible trio of points. We'll check each trio to see if they form a valid boomerang pattern based on distance. We'll count the number of trios that meet our criteria.

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

Take the first point from your collection of points.
Now, consider every possible pair of other points alongside this first point, making a trio.
For each trio, calculate the distances between the first point and the other two points in the trio.
Check if the two distances you calculated are equal. If they are, this trio might be a boomerang.
If the distances are equal, add one to your count of boomerangs.
Repeat this process by selecting the second point from your collection, and then the third, and so on, until you've tried every point as the 'center' of a potential boomerang.
The final count represents the total number of boomerangs found by checking every possible combination.

Code Implementation

def number_of_boomerangs_brute_force(points):
    number_of_boomerangs = 0

    for index_first_point in range(len(points)):
        for index_second_point in range(len(points)):
            # Ensure second point is different from the first.
            if index_first_point == index_second_point:
                continue

            for index_third_point in range(len(points)):
                # Ensure third point is different from the first and second.
                if index_first_point == index_third_point or index_second_point == index_third_point:
                    continue

                point_a = points[index_first_point]
                point_b = points[index_second_point]
                point_c = points[index_third_point]

                distance_ab = (point_a[0] - point_b[0])**2 + (point_a[1] - point_b[1])**2
                distance_ac = (point_a[0] - point_c[0])**2 + (point_a[1] - point_c[1])**2

                # Check if the distances from first to second and first to third are equal.
                if distance_ab == distance_ac:
                    number_of_boomerangs += 1

    return number_of_boomerangs

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through each of the n points in the input array. For each point, it considers every possible pair of the remaining points to form a trio. Finding every possible pair of the other points can be seen as a nested loop, thus O(n^2). For each of these trios, calculating the distances takes constant time, and the comparison also takes constant time. Therefore, the overall time complexity is approximately n * n^2 which simplifies to O(n^3).

Space Complexity

O(1) – The provided algorithm calculates distances between points without using any auxiliary data structures that scale with the input size N (where N is the number of points). It only uses a few constant space variables to store intermediate distance calculations and a boomerang counter. Therefore, the space complexity remains constant regardless of the input size. In conclusion, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key is to focus on each point and count how many other points are the same distance away from it. Then, for each point, use the count of points at the same distance to quickly determine the number of boomerangs that can be formed with that point as the center, without checking all possible combinations.

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

For each point in the set of points, consider it as the potential middle point of a boomerang.
For the chosen middle point, calculate the distance to all the other points.
Count how many points are at each unique distance from the chosen middle point. Store these counts efficiently.
For each distance, if there are 'n' points at that distance from the middle point, calculate the number of boomerangs that can be formed using those points. This calculation involves multiplying the number of points by the number of points minus one (n * (n-1)).
Add the number of boomerangs found for each distance to a running total.
Repeat steps 1 through 5 for every point in the set of points.
The final total will be the total number of boomerangs in the set.

Code Implementation

def number_of_boomerangs(points):
    number_of_boomerangs_found = 0

    for point_index in range(len(points)):
        distances = {}

        # Iterate through all other points to calculate distances.
        for other_point_index in range(len(points)):
            if point_index != other_point_index:
                point_x, point_y = points[point_index]
                other_point_x, other_point_y = points[other_point_index]

                distance = (point_x - other_point_x)**2 + (point_y - other_point_y)**2

                if distance not in distances:
                    distances[distance] = 0
                distances[distance] += 1

        # Calculate boomerangs based on point counts at each distance.
        for distance_value in distances:
            number_of_points_at_distance = distances[distance_value]
            # Boomerang count: n * (n - 1) permutations
            number_of_boomerangs_found += number_of_points_at_distance * (number_of_points_at_distance - 1)

    return number_of_boomerangs_found

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n points in the input array. The inner operations calculate distances from the current point to all other n-1 points. This distance calculation and the subsequent counting of points at each distance takes O(n) time per outer loop iteration. Therefore, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The algorithm iterates through each point and, for each point, calculates distances to all other points. Crucially, a data structure (likely a hash map or dictionary) is used to store the counts of points at each unique distance from the chosen middle point. In the worst case, all other points are at different distances, meaning the hash map will store N-1 distances and their associated counts, where N is the number of points. Therefore, the auxiliary space scales linearly with the number of points, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no boomerangs can be formed.
Array with less than 3 points	Return 0 as at least 3 points are required to form a boomerang.
All points are the same	The distance between each pair will be 0, leading to n*(n-1) boomerangs from that single point which can cause integer overflow; use long for distances to avoid overflow.
Integer overflow in distance calculation (xx + yy)	Use long data type to store the square of the differences to avoid integer overflow during distance calculation.
Large input array (performance consideration)	The O(n^2) solution may become slow; optimize distance calculation if possible or consider more efficient data structures if available with further problem constraints.
Points with extremely large coordinate values	Using a long datatype for intermediate calculations will prevent potential overflow with very large squared differences.
Points are collinear (lying on the same line)	The hash map correctly counts distances even when points are collinear.
Duplicate points in the array	Duplicate points will be treated as distinct points when calculating distances.

Null or empty input array

How to Handle:

Return 0 immediately as no boomerangs can be formed.

Array with less than 3 points

How to Handle:

Return 0 as at least 3 points are required to form a boomerang.

All points are the same

How to Handle:

The distance between each pair will be 0, leading to n*(n-1) boomerangs from that single point which can cause integer overflow; use long for distances to avoid overflow.

Integer overflow in distance calculation (x*x + y*y)

How to Handle:

Use long data type to store the square of the differences to avoid integer overflow during distance calculation.

Large input array (performance consideration)

How to Handle:

The O(n^2) solution may become slow; optimize distance calculation if possible or consider more efficient data structures if available with further problem constraints.

Points with extremely large coordinate values

How to Handle:

Using a long datatype for intermediate calculations will prevent potential overflow with very large squared differences.

Points are collinear (lying on the same line)

How to Handle:

The hash map correctly counts distances even when points are collinear.

Duplicate points in the array

How to Handle:

Duplicate points will be treated as distinct points when calculating distances.

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 expected range of the x and y coordinates? Can they be negative?
What is the size of the input array? Should I be concerned about exceeding memory limits?
If there are no boomerangs, what value should I return? Should I return 0?
Can points overlap (i.e., have identical coordinates)? If so, how should that be handled?
Is the order of points within a boomerang important? For example, is (i, j, k) considered different from (i, k, j)?

Brute Force Solution

Approach

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

Take the first point from your collection of points.
Now, consider every possible pair of other points alongside this first point, making a trio.
For each trio, calculate the distances between the first point and the other two points in the trio.
Check if the two distances you calculated are equal. If they are, this trio might be a boomerang.
If the distances are equal, add one to your count of boomerangs.
Repeat this process by selecting the second point from your collection, and then the third, and so on, until you've tried every point as the 'center' of a potential boomerang.
The final count represents the total number of boomerangs found by checking every possible combination.

Code Implementation

def number_of_boomerangs_brute_force(points):
    number_of_boomerangs = 0

    for index_first_point in range(len(points)):
        for index_second_point in range(len(points)):
            # Ensure second point is different from the first.
            if index_first_point == index_second_point:
                continue

            for index_third_point in range(len(points)):
                # Ensure third point is different from the first and second.
                if index_first_point == index_third_point or index_second_point == index_third_point:
                    continue

                point_a = points[index_first_point]
                point_b = points[index_second_point]
                point_c = points[index_third_point]

                distance_ab = (point_a[0] - point_b[0])**2 + (point_a[1] - point_b[1])**2
                distance_ac = (point_a[0] - point_c[0])**2 + (point_a[1] - point_c[1])**2

                # Check if the distances from first to second and first to third are equal.
                if distance_ab == distance_ac:
                    number_of_boomerangs += 1

    return number_of_boomerangs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

For each point in the set of points, consider it as the potential middle point of a boomerang.
For the chosen middle point, calculate the distance to all the other points.
Count how many points are at each unique distance from the chosen middle point. Store these counts efficiently.
For each distance, if there are 'n' points at that distance from the middle point, calculate the number of boomerangs that can be formed using those points. This calculation involves multiplying the number of points by the number of points minus one (n * (n-1)).
Add the number of boomerangs found for each distance to a running total.
Repeat steps 1 through 5 for every point in the set of points.
The final total will be the total number of boomerangs in the set.

Code Implementation

def number_of_boomerangs(points):
    number_of_boomerangs_found = 0

    for point_index in range(len(points)):
        distances = {}

        # Iterate through all other points to calculate distances.
        for other_point_index in range(len(points)):
            if point_index != other_point_index:
                point_x, point_y = points[point_index]
                other_point_x, other_point_y = points[other_point_index]

                distance = (point_x - other_point_x)**2 + (point_y - other_point_y)**2

                if distance not in distances:
                    distances[distance] = 0
                distances[distance] += 1

        # Calculate boomerangs based on point counts at each distance.
        for distance_value in distances:
            number_of_points_at_distance = distances[distance_value]
            # Boomerang count: n * (n - 1) permutations
            number_of_boomerangs_found += number_of_points_at_distance * (number_of_points_at_distance - 1)

    return number_of_boomerangs_found

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no boomerangs can be formed.
Array with less than 3 points	Return 0 as at least 3 points are required to form a boomerang.
All points are the same	The distance between each pair will be 0, leading to n*(n-1) boomerangs from that single point which can cause integer overflow; use long for distances to avoid overflow.
Integer overflow in distance calculation (xx + yy)	Use long data type to store the square of the differences to avoid integer overflow during distance calculation.
Large input array (performance consideration)	The O(n^2) solution may become slow; optimize distance calculation if possible or consider more efficient data structures if available with further problem constraints.
Points with extremely large coordinate values	Using a long datatype for intermediate calculations will prevent potential overflow with very large squared differences.
Points are collinear (lying on the same line)	The hash map correctly counts distances even when points are collinear.
Duplicate points in the array	Duplicate points will be treated as distinct points when calculating distances.

Null or empty input array

How to Handle:

Return 0 immediately as no boomerangs can be formed.

Array with less than 3 points

How to Handle:

Return 0 as at least 3 points are required to form a boomerang.

All points are the same

How to Handle:

The distance between each pair will be 0, leading to n*(n-1) boomerangs from that single point which can cause integer overflow; use long for distances to avoid overflow.

Integer overflow in distance calculation (x*x + y*y)

How to Handle:

Use long data type to store the square of the differences to avoid integer overflow during distance calculation.

Large input array (performance consideration)

How to Handle:

The O(n^2) solution may become slow; optimize distance calculation if possible or consider more efficient data structures if available with further problem constraints.

Points with extremely large coordinate values

How to Handle:

Using a long datatype for intermediate calculations will prevent potential overflow with very large squared differences.

Points are collinear (lying on the same line)

How to Handle:

The hash map correctly counts distances even when points are collinear.

Duplicate points in the array

How to Handle:

Duplicate points will be treated as distinct points when calculating distances.

0/1916 Google questions completed

0/1916 completed