# O(n^2lgn) solutions only takes 519ms while O(n^2) takes 789ms, test cases need to be updated

• The test cases need to be updated.

O(n^2lgn) using sort takes 519ms beating 100%
while O(n^2) using hashmap takes 789 ms(still beating 100% wtf? maybe not enough submissions yet)

here's the solutions

O(n^2lgn):

``````class Solution {
public:
typedef pair<int,int> Point;
int numberOfBoomerangs(vector<pair<int, int>>& points) {
const size_t n = points.size();
int result = 0;
vector<int> dists;
dists.reserve(n - 1);
for (int i = 0; i < n; ++i) {
dists.clear();
const auto& point = points[i];
for (int j = 0; j < n; ++j) {
if (i == j) continue;
dists.push_back(dist(points[j], point));
}
sort(dists.begin(), dists.end());
int start = 0;
for (int j = 1; j < n - 1; ++j) {
if (dists[j] == dists[start]) {
result += (j - start) * 2;
} else {
start = j;
}
}
}
return result;
}
private:
static int dist(const Point& a, const Point& b) {
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
};
``````

O(n^2):

``````class Solution {
public:
typedef pair<int,int> Point;
int numberOfBoomerangs(vector<pair<int, int>>& points) {
const size_t n = points.size();
int result = 0;
unordered_map<int,int> counts;
for (int i = 0; i < n; ++i) {
const auto& point = points[i];
counts.clear();
for (int j = 0; j < n; ++j) {
if (i == j) continue;
auto& count = counts[dist(point, points[j])];
result += 2 * count++;
}
}
return result;
}
private:
static int dist(const Point& a, const Point& b) {
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.