Number of Boomerangs solution and explanation
Google
9 more videos on this problem
447. Number of Boomerangs | LEETCODE MEDIUMcode Explainer · 6:53 · 2K views
447. Number of Boomerangs (Leetcode Easy)Programming Live with Larry · 10:20 · 1K views
LeetCode in Python 447. Number of Boomerangs - Michelle小梦想家Michelle小梦想家 · 12:19 · 1K views
LeetCode 447. Number Of Boomerang, Data Structure & AlgorithmSourabh Saraswat · 39:57 · 534 views
(C#)LeetCode 447 Number of Boomerangszongwu yang · 7:38 · 384 views
Number of Boomerangs LeetCodeHustler Den · 4:33 · 342 views
Number Of Boomerangs | Leetcode | Java | Solution | ExplanationCodingWithTricks · 10:39 · 313 views
Number of Boomerangs | LeetCode 447 | HashMap + Geometry Logic Explained | Python DSANidhi Chouhan · 24:18 · 36 views
No Sound Leetcode 447: Number of BoomerangsExtremeProgrammer · 1:18 · 25 views
LeetCode 447: Number of BoomerangsAlitaCode · 30:18 · 8 views
The 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.
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.length1 <= n <= 500points[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.
from collections import defaultdict
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
n = len(points)
count = 0
for i in range(n):
dist_map = defaultdict(int)
for j in range(n):
if i == j:
continue
dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]
dist = dx * dx + dy * dy
dist_map[dist] += 1
for value in dist_map.values():
count += value * (value - 1)
return countimport java.util.HashMap;
import java.util.Map;
public class Solution {
public int numberOfBoomerangs(int[][] points) {
int n = points.length;
int count = 0;
for (int i = 0; i < n; ++i) {
Map<Integer, Integer> distMap = new HashMap<>();
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int dist = dx * dx + dy * dy;
distMap.put(dist, distMap.getOrDefault(dist, 0) + 1);
}
for (int value : distMap.values()) {
count += value * (value - 1);
}
}
return count;
}
}#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int n = points.size();
int count = 0;
for (int i = 0; i < n; ++i) {
unordered_map<int, int> distMap;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int dist = dx * dx + dy * dy;
distMap[dist]++;
}
for (auto& entry : distMap) {
count += entry.second * (entry.second - 1);
}
}
return count;
}
};function numberOfBoomerangs(points) {
let count = 0;
const n = points.length;
for (let i = 0; i < n; i++) {
const distMap = new Map();
for (let j = 0; j < n; j++) {
if (i === j) continue;
const dx = points[i][0] - points[j][0];
const dy = points[i][1] - points[j][1];
const dist = dx * dx + dy * dy;
distMap.set(dist, (distMap.get(dist) || 0) + 1);
}
distMap.forEach(value => {
count += value * (value - 1);
});
}
return count;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 500
int numberOfBoomerangs(int** points, int pointsSize, int* pointsColSize) {
int count = 0;
int dist[SIZE] = {0}; // Assuming max dist
for (int i = 0; i < pointsSize; ++i) {
memset(dist, 0, sizeof(dist));
for (int j = 0; j < pointsSize; ++j) {
if (i == j) continue;
int d = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
dist[d]++;
}
for (int k = 0; k < SIZE; ++k) {
if (dist[k] > 0) {
count += dist[k] * (dist[k] - 1);
}
}
}
return count;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumberOfBoomerangs(int[][] points) {
int n = points.Length;
int count = 0;
for (int i = 0; i < n; ++i) {
Dictionary<int, int> distMap = new Dictionary<int, int>();
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int dist = dx * dx + dy * dy;
if (!distMap.ContainsKey(dist)) {
distMap[dist] = 0;
}
distMap[dist]++;
}
foreach (var entry in distMap) {
count += entry.Value * (entry.Value - 1);
}
}
return count;
}
}This Python implementation uses `defaultdict` to automatically handle new distances and track their counts. It iterates through points, calculates distances, and uses the counts to calculate possible boomerangs.
Time complexity is O(n^2), and space complexity is O(n) due to the defaultdict used for counting distances.
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.
from collections import defaultdict
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
n = len(points)
count = 0
unique_distances = set()
for i in range(n):
dist_map = defaultdict(int)
for j in range(n):
if i == j:
continue
dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]
dist = dx * dx + dy * dy
dist_map[dist] += 1
unique_distances.add(dist)
for value in dist_map.values():
count += value * (value - 1)
return countimport java.util.HashMap;
import java.util.Map;
public class Solution {
public int numberOfBoomerangs(int[][] points) {
int n = points.length;
int count = 0;
Map<Integer, Integer> lookup = new HashMap<>(); // Lookup table
for (int i = 0; i < n; ++i) {
Map<Integer, Integer> distMap = new HashMap<>();
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[i][1];
int dist = dx * dx + dy * dy;
if (!lookup.containsKey(dist)) {
lookup.put(dist, dist); // Just for demonstration, not needed actually
}
distMap.put(dist, distMap.getOrDefault(dist, 0) + 1);
}
for (int value : distMap.values()) {
count += value * (value - 1);
}
}
return count;
}
}#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int n = points.size();
int count = 0;
vector<int> precomputed_sq_dist(n * 2, 0);
for (int i = 0; i < n; ++i) {
unordered_map<int, int> distMap;
for (int j = 0; j < n; ++j) {
if (i != j) {
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int dist = precomputed_sq_dist[dx + dy];
distMap[dist]++;
}
}
for (auto& entry : distMap) {
count += entry.second * (entry.second - 1);
}
}
return count;
}
};function numberOfBoomerangs(points) {
let count = 0;
const uniqueDistances = new Set();
const n = points.length;
for (let i = 0; i < n; i++) {
const distMap = new Map();
for (let j = 0; j < n; j++) {
if (i === j) continue;
const dx = points[i][0] - points[j][0];
const dy = points[i][1] - points[j][1];
const dist = dx * dx + dy * dy;
uniqueDistances.add(dist);
distMap.set(dist, (distMap.get(dist) || 0) + 1);
}
distMap.forEach(value => {
count += value * (value - 1);
});
}
return count;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_DIST 100000
int numberOfBoomerangs(int** points, int pointsSize, int* pointsColSize) {
int count = 0;
int *dist = (int*)malloc(MAX_DIST * sizeof(int));
for (int i = 0; i < pointsSize; ++i) {
memset(dist, 0, MAX_DIST * sizeof(int));
for (int j = 0; j < pointsSize; ++j) {
if (i == j) continue;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int sqDist = dx * dx + dy * dy;
dist[sqDist]++;
}
for (int k = 0; k < MAX_DIST; ++k) {
if (dist[k] > 1) {
count += dist[k] * (dist[k] - 1);
}
}
}
free(dist);
return count;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumberOfBoomerangs(int[][] points) {
int n = points.Length;
int count = 0;
HashSet<int> uniqueDistances = new HashSet<int>();
for (int i = 0; i < n; ++i) {
Dictionary<int, int> distMap = new Dictionary<int, int>();
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int dist = dx * dx + dy * dy;
if (!uniqueDistances.Contains(dist)) {
uniqueDistances.Add(dist);
}
if (!distMap.ContainsKey(dist)) {
distMap[dist] = 0;
}
distMap[dist]++;
}
foreach (var entry in distMap) {
count += entry.Value * (entry.Value - 1);
}
}
return count;
}
}This Python solution stores distances in a set to highlight pre-computation but doesn't actively use it beyond uniqueness count. It's primarily demonstrative.
Time complexity is O(n^2), and it incurs extra space for storing set of all possible distances.
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.
function numberOfBoomerangs(points: number[][]): number {
let ans = 0;
for (const [x1, y1] of points) {
const cnt: Map<number, number> = new Map();
for (const [x2, y2] of points) {
const d = (x1 - x2) ** 2 + (y1 - y2) ** 2;
ans += cnt.get(d) || 0;
cnt.set(d, (cnt.get(d) || 0) + 1);
}
}
return ans << 1;
}func numberOfBoomerangs(points [][]int) (ans int) {
for _, p1 := range points {
cnt := map[int]int{}
for _, p2 := range points {
d := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
ans += cnt[d]
cnt[d]++
}
}
ans <<= 1
return
}Approach 4: Default Approach
function numberOfBoomerangs(points: number[][]): number {
let ans = 0;
for (const [x1, y1] of points) {
const cnt: Map<number, number> = new Map();
for (const [x2, y2] of points) {
const d = (x1 - x2) ** 2 + (y1 - y2) ** 2;
cnt.set(d, (cnt.get(d) || 0) + 1);
}
for (const [_, x] of cnt) {
ans += x * (x - 1);
}
}
return ans;
}func numberOfBoomerangs(points [][]int) (ans int) {
for _, p1 := range points {
cnt := map[int]int{}
for _, p2 := range points {
d := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
cnt[d]++
}
for _, x := range cnt {
ans += x * (x - 1)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Distance Counting using HashMap | Time complexity is O(n^2), and space complexity is O(n) due to the defaultdict used for counting distances. |
| Approach 2: Pre-computation and Lookup Table | Time complexity is O(n^2), and it incurs extra space for storing set of all possible distances. |
| Enumeration + Counting | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Distance Counting using HashMap | O(n^2) | O(n) | General case and interview settings where memory efficiency and clarity matter |
| Pre-computation with Distance Lookup Table | O(n^2) | O(n^2) | Useful if distances will be reused many times or precomputation is acceptable |
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.