Number of Boomerangs - Practice Coding Problems

Number of Boomerangs - Problem

You are given n points in the plane that are all distinct, where points[i] = [xi, yi].

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.

Input & Output

Example 1 — Basic Boomerangs

$ Input: points = [[0,0],[1,0],[2,0]]

› Output: 2

💡 Note: Two boomerangs exist: (1,0,2) because distance from [1,0] to [0,0] equals distance from [1,0] to [2,0] (both = 1), and (0,1,2) because distance from [0,0] to [1,0] equals distance from [0,0] to [2,0] (both = 1). Wait, let me recalculate: From [1,0]: dist to [0,0] = 1, dist to [2,0] = 1, so (1,0,2) is valid. From [0,0]: dist to [1,0] = 1, dist to [2,0] = 2, not equal. From [2,0]: dist to [0,0] = 2, dist to [1,0] = 1, not equal. Actually, only 2 boomerangs: (1,0,2) and (1,2,0).

Example 2 — Square Formation

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

› Output: 2

💡 Note: Points form a diagonal line. From [2,2]: distance to [1,1] = √2, distance to [3,3] = √2. So (2,1,3) and (2,3,1) are valid boomerangs.

Example 3 — No Boomerangs

$ Input: points = [[1,1]]

› Output: 0

💡 Note: Only one point exists, so no boomerangs can be formed (need at least 3 points).

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given array of coordinate points

Find Equal Distances

For each center point, find pairs at equal distances

Count Boomerangs

Sum all valid boomerang combinations

Key Takeaway

🎯 Key Insight: Use hash map to group points by distance from each center

Asked in

G Google 15 a Amazon 12 🍎 Apple 8

The key insight is that for each point as center, we need to count how many pairs of other points are equidistant from it. Best approach uses hash map frequency counting to achieve O(n²) time instead of O(n³). For each distance with k points, we can form k*(k-1) ordered boomerangs. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Group by Distance	O(n²)	O(n)	For each point, use hash map to count points at same distance
Brute Force - Check All Triplets	O(n³)	O(1)	Check every possible combination of three points

Hash Map - Group by Distance — Algorithm Steps

Step 1: For each point as potential center
Step 2: Calculate distances to all other points and count frequencies
Step 3: For each distance with count k, add k*(k-1) boomerangs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int distance;
    int count;
} DistEntry;

int solution(int** points, int pointsSize) {
    int count = 0;
    
    for (int i = 0; i < pointsSize; i++) {
        DistEntry distances[500];
        int distCount = 0;
        
        for (int j = 0; j < pointsSize; j++) {
            if (i != j) {
                int dist = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + 
                          (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                
                int found = 0;
                for (int d = 0; d < distCount; d++) {
                    if (distances[d].distance == dist) {
                        distances[d].count++;
                        found = 1;
                        break;
                    }
                }
                
                if (!found) {
                    distances[distCount].distance = dist;
                    distances[distCount].count = 1;
                    distCount++;
                }
            }
        }
        
        for (int d = 0; d < distCount; d++) {
            int k = distances[d].count;
            count += k * (k - 1);
        }
    }
    
    return count;
}

int main() {
    char buffer[10000];
    fgets(buffer, sizeof(buffer), stdin);
    
    int points[500][2];
    int** pointPtrs = malloc(500 * sizeof(int*));
    int pointsSize = 0;
    
    char* token = strtok(buffer, "[],\n");
    while (token != NULL && pointsSize < 500) {
        if (strlen(token) > 0 && strchr(token, ' ') == NULL) {
            points[pointsSize][0] = atoi(token);
            token = strtok(NULL, "[],\n");
            if (token != NULL) {
                points[pointsSize][1] = atoi(token);
                pointPtrs[pointsSize] = points[pointsSize];
                pointsSize++;
            }
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(pointPtrs, pointsSize));
    free(pointPtrs);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each point, we calculate distances to all other points

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores at most n distance counts per iteration

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen