Skip to main content
Talentd

Number of Boomerangs - Solution & Explanation

MediumArrayHash TableMath17 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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.

 

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
  • -104 <= xi, yi <= 104
  • All the points are unique.

Approach Overview

Problem Overview: You are given a list of 2D points. A boomerang is an ordered tuple of points (i, j, k) where the distance from i to j equals the distance from i to k. Order matters, so (i, j, k) and (i, k, j) count as different boomerangs. The goal is to count all such tuples across the set of points.

Approach 1: Distance Counting using HashMap (Time: O(n^2), Space: O(n))

Fix one point as the center i. Compute the squared Euclidean distance from i to every other point. Store frequencies of these distances in a HashMap. If a particular distance appears k times, it forms k * (k - 1) ordered pairs because each pair of points at that distance can be arranged in two directions. This approach avoids unnecessary square roots by using squared distance calculations and relies on constant-time hash lookups. The algorithm iterates through all points as centers, making it an efficient hash table based solution combined with simple array iteration.

Approach 2: Pre-computation and Lookup Table (Time: O(n^2), Space: O(n^2))

Instead of recomputing distances for each center point, precompute the pairwise squared distances between every pair of points and store them in a lookup table or matrix. After building this table, iterate over each center i and count how many points share the same distance value relative to i. Use the same combinational formula k * (k - 1) to count ordered pairs. This approach reduces repeated distance calculations but increases memory usage due to the stored matrix. The logic still relies on geometric distance properties from basic math operations.

Recommended for interviews: The hash map distance counting approach is what most interviewers expect. It demonstrates understanding of frequency counting, avoiding redundant work, and translating a geometric condition into a counting problem. Pre-computation can work but uses unnecessary memory. Showing the brute reasoning first (compare distances from a fixed center) and then optimizing with a hash map signals strong problem‑solving skills.

Approach 1: Approach 1: Distance Counting using HashMap

This approach involves treating each point as a base point and calculating the distance to all other points. A hashmap (or dictionary) is used to count occurrences of each distance. For any two points that share the same distance to the base point, we have two boomerangs.

We use a fixed-size array `dist` to store the count of distances from the base point to all other points. For each pair of points with the same distance, two boomerangs can be formed. The array `dist` is reset on every iteration to count new distances for the next base point.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n^2) where n is the number of points, and space complexity is O(SIZE) for the distance count array.

Try this approach in the editor →

Approach 2: Approach 2: Pre-computation and Lookup Table

This approach involves using a lookup table to pre-compute square distance values. This can reduce some computational overhead during the distance calculation step by avoiding repetitive arithmetic operations.

In this implementation, a static array `dist` is used to store pre-computed square distances for efficient access. The cost of setting up the lookup table is offset by faster access during distance retrieval.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity remains O(n^2), but the space complexity is larger due to the MAX_DIST array.

Try this approach in the editor →

Approach 3: Enumeration + Counting

We can enumerate each point in points as the boomerang's point i, and then use a hash table cnt to record the number of times the distance from other points to i appears.

If there are x points with equal distance to i, then we can arbitrarily select two of them as the boomerang's j and k. The number of schemes is A_x^2 = x times (x - 1). Therefore, for each value x in the hash table, we calculate and accumulate A_x^2, which gives us the total number of boomerangs that meet the problem's requirements.

The time complexity is O(n^2), and the space complexity is O(n), where n is the length of the array points.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Distance Counting using HashMap

Time complexity is O(n^2) where n is the number of points, and space complexity is O(SIZE) for the distance count array.

Approach 2: Pre-computation and Lookup Table

Time complexity remains O(n^2), but the space complexity is larger due to the MAX_DIST array.

Enumeration + Counting—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Distance Counting using HashMapO(n^2)O(n)General case and interview settings where memory efficiency and clarity matter
Pre-computation with Distance Lookup TableO(n^2)O(n^2)Useful if distances will be reused many times or precomputation is acceptable

Video Solution

447. Number of Boomerangs | LEETCODE MEDIUM • code Explainer • 2,481 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Boomerangs easy or hard?
Number of Boomerangs is rated Medium because the brute-force idea is straightforward but recognizing the frequency counting trick with k * (k - 1) requires insight. Once that observation is made, the implementation becomes simple.
Number of Boomerangs Python/Java solution
Python typically uses a dictionary or collections.defaultdict to count distances, while Java uses HashMap<Integer, Integer>. Both implementations iterate through each point as a center and accumulate k * (k - 1) for matching distances.
How to solve Number of Boomerangs in O(n^2)?
Iterate through each point as the center i. Compute the squared distance from i to every other point and store counts in a hash map. If a distance appears k times, add k * (k - 1) to the answer since order matters between j and k.
What is the best approach for Number of Boomerangs?
The most efficient approach fixes each point as the center and counts distances to all other points using a hash map. For every distance that appears k times, it contributes k * (k - 1) ordered boomerangs. This runs in O(n^2) time and O(n) space and is the standard interview solution.
Is Number of Boomerangs asked at Google/Amazon/Meta?
Problems involving distance grouping, hash map counting, and geometric reasoning appear frequently in interviews at companies like Google, Amazon, and Meta. Number of Boomerangs tests the ability to transform a geometric condition into a counting problem using hashing.
What data structure is used in Number of Boomerangs?
A hash table (HashMap or dictionary) is the primary data structure. It stores the frequency of squared distances from a fixed center point to all other points, enabling constant-time updates and lookups while counting boomerangs.
What is the time complexity of Number of Boomerangs?
The optimal solution runs in O(n^2) time because for each point you compute distances to every other point. The hash map stores frequency counts of distances for that center. Space complexity is O(n) for the distance frequency map.

Ready to solve this problem?

Practice Number of Boomerangs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Line Reflection