algoadvance

Leetcode 447. Number of Boomerangs

Problem Statement

The problem is taken from LeetCode (#447: Number of Boomerangs).

Given n points in the plane that are all pairwise distinct, 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).

You need to calculate the number of boomerangs.

Clarifying Questions

1. Input Format:
   • The input is given as a vector of points where each point is represented as a vector of two integers [x, y].
2. Output Format:
   • The output is a single integer representing the number of boomerangs.
3. Constraints:
   • All the points are distinct.
   • The number of points, n, can be up to 500.
   • The coordinates of points are integers.

Strategy

1. For each point, compute the squared distances to all other points and store the frequency of each distance in a hash map.
2. For each distance with frequency f, the number of boomerangs is f * (f - 1), as points can be permuted in two positions (i, j, k) or (i, k, j).

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size();
        int result = 0;

        for (int i = 0; i < n; ++i) {
            unordered_map<int, int> distanceFreq;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int dist = getDistanceSquared(points[i], points[j]);
                distanceFreq[dist]++;
            }
            for (auto& d : distanceFreq) {
                int count = d.second;
                result += count * (count - 1);
            }
        }
        return result;
    }

private:
    int getDistanceSquared(const vector<int>& p1, const vector<int>& p2) {
        int dx = p1[0] - p2[0];
        int dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
};

Time Complexity

• Time Complexity: (O(n^2)), where n is the number of points. The double loop iterates through all pairs of points.
• Space Complexity: (O(n)) for the hashmap that holds the distance frequencies for each fixed point.

This approach ensures that we comprehensively count all possible boomerangs by leveraging the distance frequency count efficiently for each point.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?