My O(nlogn) sort, O(1) space, no fp C++ solution


  • 0
    S
    class Solution {
    public:
        bool isReflected(vector<pair<int, int>>& points) {
            if (points.empty()) return true;
            
            int minx = INT_MAX;
            int maxx = INT_MIN;
            for (auto& p : points) {
                p.first *= 2; // Avoid float
                minx = min(minx, p.first);
                maxx = max(maxx, p.first);
            }
            int center = (minx + maxx)/2;
            for (auto& p : points) p.first -= center;
            
            sort(points.begin(), points.end(),
                 [](const pair<int, int>& a, const pair<int, int>& b) {
                     return (a.second != b.second) ? (a.second < b.second) : (abs(a.first)<abs(b.first));
                 });
            
            int px = 0, py = 0;
            int plus = 1, minus = 1;
            for (int i=0; i<points.size(); ++i) {
                if (px!=abs(points[i].first) || py!=points[i].second) {
                    if (!(plus>0 && minus>0)) return false;
                    px = abs(points[i].first);
                    py = points[i].second;
                    plus = 0;
                    minus = 0;
                }
                plus += (points[i].first>=0);
                minus += (points[i].first<=0);
            }
            
            return (plus>0 && minus>0);
        }
    };
    

Log in to reply
 

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