Two sorts to solve the problem


  • 0

    The Idea is to use two sorts.
    The first sort will sort the points based on their x coordinates, when x are the same, smaller y comes first.
    The second sort will sort the second half of the points by x coordinates, but with larger y comes first.
    An example could be like:

    [(-5,-2), (-1,-2), (-1,0), (1,0), (1,-2), (5, -2)].

    After sorting, we just remove repeated points and points on the line. Then check if the rest points can be matched.

    bool isReflected(vector<pair<int, int>>& points) {
        int n = points.size();
        if(n <= 1) {
            return true;
        }
        
        // sort the points, based on x coordinates
        sort(points.begin(), points.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
            if(p1.first == p2.first) {
                return p1.second < p2.second;
            }    
            else {
                return p1.first < p2.first;
            }
        });
        
        // Then sort the second half, such that p1.second > p2.second comes first
        sort(points.begin()+n/2, points.end(), [](const pair<int, int>&p1, const pair<int, int>& p2) {
            if(p1.first == p2.first) {
                return p1.second > p2.second;
            }    
            else {
                return p1.first < p2.first;
            }
        });
        
        int axis = points[0].first + points[n-1].first;
        
        // Remove (put them at back) repeat points and points on the axis
        int storeIndex = 0;
        for(int i = 0; i < n; i++) {
            // Do not consider repeat points
            if(i > 0 && (points[i].first == points[i-1].first && points[i].second == points[i-1].second)) {
                continue;
            }
            
            if(points[i].first*2 == axis) {
                continue;
            }
            
            points[storeIndex++] = points[i];
        }
        
        int i = 0;
        int j = storeIndex-1;
        for( ;i <= j; ) {
            
            // update i and j position
            i++;
            while((points[i-1].first == points[i].first && points[i-1].second == points[i].second)
                   || points[i].first*2 == axis) {
                i += 1;
                if(i >= j) {
                    break;
                }
            }
            
            j--;
            while((points[j+1].first == points[j].first && points[j+1].second == points[j].second)
                   || points[j].first*2 == axis) {
                j -= 1;
                if(j <= i) {
                    break;
                }
            }
            
            // Not symetric or y coordinate not same
            if(points[i].first + points[j].first != axis || points[i].second != points[j].second) {
                return false;
            } 
        }
        
        return true;
    }

Log in to reply
 

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