Does it exist O(1) space and <O(n^3) time solution?


  • 0
    W

    What if the interviewer require O(1) space? Here I provide my working solution with O(N^3) time and O(1) space, in case the aforementioned follow up. Note that due to the high time complexity, it cannot be accepted by Leetcode. The idea is based on the observation that if the distance between i and j equals the distance between i and k, i must be at the midperpendicular of segment (k, j). So we just check how many points locate at the midperpendicular of each pair of points. To quickly check if a point i locate at the midperpendicular of pair (j, k), line (i, mid) and line (k, j) must be orthogonal, where mid is the midpoint of segment (k, j). To check this condition, we can use the geometry knowledge, Vector(i, mid) * Vector(j, k) == 0.

    Knows more solutions doesn't hurt : )

    int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int count = 0, n = points.size();
            for(int i = 0; i < n-1; i++) {
                for(int j = i+1; j < n; j++) {
                    int x1 = points[i].first, y1 = points[i].second;
                    int x2 = points[j].first, y2 = points[j].second;
                    double midx = 1.0 * (x1 + x2) / 2;
                    double midy = 1.0 * (y1 + y2) / 2;
                    for(int k = 0; k < n; k++) {
                        if(k == i || k == j) continue;
                        int x3 = points[k].first, y3 = points[k].second;
                        double vecProd = 1.0 * (x3 - midx) * (x1 - x2) + 1.0 * (y3 - midy) * (y1 - y2);
                        if(vecProd == 0) count += 2;
                    }
                }
            }
            return count;
        }
    

Log in to reply
 

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