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


  • 0
    A

    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);
        }
    };
    

Log in to reply
 

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