Number Of Boomerangs Problem


Description

LeetCode Problem 447.

You are given n points in the plane that are all distinct, where points[i] = [x_i, y_i]. 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:

1
2
3
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:

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

Example 3:

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

Constraints:

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -10^4 <= x_i, y_i <= 10^4
  • All the points are unique.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int boom = 0;
        int n = points.size();
        if (n < 3) return 0;
       
        for (int i = 0; i < n; i++){
            map<int, int> mp;
            for (int j = 0; j < n; j++){
                if (i == j) continue;
                int dist = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]);
                dist += ((points[i][1] - points[j][1]) * (points[i][1] - points[j][1]));
                mp[dist]++;
            }
            
            for (auto it : mp){
                if (it.second <= 1) continue;
                boom += (it.second * (it.second - 1));
            }
        }
        return boom;
    }
};




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Vowel Spellchecker Problem

LeetCode 966. Given a wordlist, we want to implement a...

Verifying An Alien Dictionary Problem

LeetCode 953. In an alien language, surprisingly, they also use...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...