C++ O(1) Extra space O(nlogn) Time, Clean and clear.


  • 0
    F

    Suppose the follow-up question is we don't have enough memory and you are not allowed to use extra memory other than the space these points already take.
    We can actually do it in place like this:

    struct Solution {
        bool isReflected(vector<pair<int, int>>& points) {
            if (points.empty()) return true;
            auto comp = [](pair<int, int> a, pair<int, int> b) {return a.second < b.second || (a.second == b.second && a.first < b.first);};
            sort(points.begin(), points.end(), comp);
            int k = 0;
            double central = numeric_limits<double>::infinity();
            while(k < points.size())
            {
                auto iter = upper_bound(points.begin(), points.end(), make_pair(INT_MAX, points[k].second), comp);
                int i = k, j = iter - points.begin() - 1;
                while (i <= j)
                {
                    if (central == numeric_limits<double>::infinity())
                        central = (points[i].first + points[j].first) / 2.0;
                    else if ((points[i].first + points[j].first) / 2.0 != central)
                        return false;
                    i ++; j --;
                }
                k = iter - points.begin();
            }
            return true;
        }
    };
    

    Thought it contains two loops, it is easy to see why it is still O(nlogn) Time.


Log in to reply
 

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