In this guide, you will get 447. Number of Boomerangs LeetCode Solution with the best time and space complexity. The solution to Number of Boomerangs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
447. Number of Boomerangs LeetCode Solution in C++
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int ans = 0;
for (const vector<int>& p : points) {
unordered_map<int, int> distCount;
for (const vector<int>& q : points) {
const int dist = getDist(p, q);
++distCount[dist];
}
for (const auto& [_, freq] : distCount)
ans += freq * (freq - 1); // C(freq, 2)
}
return ans;
}
private:
int getDist(const vector<int>& p, const vector<int>& q) {
return pow(p[0] - q[0], 2) + pow(p[1] - q[1], 2);
}
}; /* code provided by PROGIEZ */
447. Number of Boomerangs LeetCode Solution in Java
class Solution {
public int numberOfBoomerangs(int[][] points) {
int ans = 0;
for (int[] p : points) {
Map<Integer, Integer> distCount = new HashMap<>();
for (int[] q : points) {
final int dist = (int) getDist(p, q);
distCount.merge(dist, 1, Integer::sum);
}
for (final int freq : distCount.values())
ans += freq * (freq - 1); // C(freq, 2)
}
return ans;
}
private double getDist(int[] p, int[] q) {
return Math.pow(p[0] - q[0], 2) + Math.pow(p[1] - q[1], 2);
}
} // code provided by PROGIEZ
447. Number of Boomerangs LeetCode Solution in Python
class Solution:
def numberOfBoomerangs(self, points: list[list[int]]) -> int:
ans = 0
for x1, y1 in points:
count = collections.Counter()
for x2, y2 in points:
ans += 2 * count[(x1 - x2)**2 + (y1 - y2)**2]
count[(x1 - x2)**2 + (y1 - y2)**2] += 1
return ans # code by PROGIEZ
