We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Boomerangs

Number: 447

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given n distinct points in the plane, count the number of boomerangs. A boomerang is a tuple of points (i, j, k) such that the distance between point i and j equals the distance between point i and k. Note that the order of the tuple matters.

Key Insights

  • For every point taken as the pivot i, compute the distance between i and every other point.
  • Use the squared Euclidean distance to avoid dealing with floating-point numbers.
  • Group points by the same distance from the pivot.
  • For each group with count c, there are c * (c - 1) boomerangs since the ordering of j and k matters.

Space and Time Complexity

Time Complexity: O(n^2), as for each of the n points, we compute the distance to every other point. Space Complexity: O(n), due to the hash map used to store distances for each point.

Solution

We iterate through each point considering it as the center of boomerangs. For each center, we create a hash map (or dictionary) to count how many points are at each squared distance. Once the distances are tallied, if there are count c points at a given distance, they contribute c * (c - 1) boomerang tuples. Summing these contributions yields the final count.

Code Solutions

def numberOfBoomerangs(points):
    # Initialize result counter
    result = 0
    # Loop through each point as the pivot
    for i in points:
        # Create a dictionary to count occurrences of squared distances from pivot i
        distance_count = {}
        # Compare with every other point j
        for j in points:
            dx = i[0] - j[0]  # Difference in x-coordinates
            dy = i[1] - j[1]  # Difference in y-coordinates
            dist_sq = dx * dx + dy * dy  # Squared distance to avoid float precision issues
            # Increment the count of points at this squared distance
            distance_count[dist_sq] = distance_count.get(dist_sq, 0) + 1
        # For each count found, add the number of boomerangs from that group: count * (count - 1)
        for count in distance_count.values():
            result += count * (count - 1)
    return result

# Example usage:
# print(numberOfBoomerangs([[0,0],[1,0],[2,0]]))  # Output: 2
← Back to All Questions