C++ Cached and Uncached versions.


  • 0
    A

    Uncached version. Time complexity is O(n^2).

    31 / 31 test cases passed
    Status: Accepted
    Runtime: 906 ms

    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            uint siz = points.size(), cnt = 0;
            unordered_map<uint, uint> map;
            map.reserve(siz);
            for (uint i = 0; i < siz; i++) {
                for (uint j = 0; j < siz; j++) {
                    if (i == j) continue;
                    uint dis = pow(points[j].first - points[i].first, 2) + pow(points[j].second - points[i].second, 2);
                    cnt += 2 * map[dis]++;
                }
                map.clear();
            }
            return cnt;
        }
    };
    

    Cached version. Not too much difference though. Time complexity is still O(n^2).

    31 / 31 test cases passed
    Status: Accepted
    Runtime: 846 ms

    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            uint siz = points.size(), cnt = 0;
            vector<vector<uint>> v(siz, vector<uint>(siz));
            unordered_map<uint, uint> map;
            map.reserve(siz);
            for (uint i = 0; i < siz; i++) {
                for (uint j = i+1; j < siz; j++) {
                    uint dis = pow(points[j].first - points[i].first, 2) + pow(points[j].second - points[i].second, 2);
                    v[i][j] = v[j][i] = dis;
                }
            }
            for (uint i = 0; i < siz; i++) {
                for (uint j = 0; j < siz; j++) {
                    if (i == j) continue;
                    cnt += 2 * map[v[i][j]]++;
                }
                map.clear();
            }
            return cnt;
        }
    };
    

    Unfortunately this version gets MLE when input size is huge.

    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            uint siz = points.size(), cnt = 0;
            unordered_map<unsigned long long, uint> map;
            map.reserve(siz * (siz - 1));
            for (uint i = 0; i < siz; i++) {
                for (uint j = i+1; j < siz; j++) {
                    uint dis = pow(points[j].first - points[i].first, 2) + pow(points[j].second - points[i].second, 2);
                    unsigned long long hash = (unsigned long long)dis << 32 | i;
                    cnt += 2 * map[hash]++;
                    hash = (unsigned long long)dis << 32 | j;
                    cnt += 2 * map[hash]++;
                }
            }
            return cnt;
        }
    };
    

Log in to reply
 

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