40ms C++ solution using set in the map, two pointers


  • 5
    Q

    Using set in the map to keep the x values of a particular y value sorted. The second pass iterate from the beginning and end of the set and compare with the middle line.

    bool isReflected(vector<pair<int, int>>& points) {
        int len = points.size();
        if (len==0 || len==1) return true;
        
        unordered_map<int, set<int>> mp;
        int max = points[0].first, min = points[0].first;
        // build the map, find min and max
        for (int i=0; i<len; ++i) {
            if (points[i].first < min) min = points[i].first;
            if (points[i].first > max) max = points[i].first;
            mp[points[i].second].insert(points[i].first);
        }
        double line = (min + max) / 2.0;
        
        // mirror the sorted x value in the set using two pointer
        for (auto it = mp.begin(); it!=mp.end(); ++it) {
            set<int>& s = it->second;
            for (auto start=s.begin(), end = s.end(); start!=end; ++start) {
                if ((*start + *(--end)) / 2.0 != line)
                    return false;
                if (start==end) break;
            }
        }
        return true;
    }

  • 0
    B

    Using set in a map cannot support the duplicate point case, e.g. [[1,1], [1,1], [-1, 1]]. It's better to use map in another map and compare the point count for the mirrored coordinates.


  • 0

    I have the same thought as you, here is my solution:

    bool isReflected(vector<pair<int, int>>& points) 
    {
    	int x_max = INT_MIN, x_min = INT_MAX;
    	unordered_map<int, unordered_set<int>> m;
    	for_each(points.begin(), points.end(), [&](pair<int, int> &p)
    	{ x_max = max(x_max, p.first), x_min = min(x_min, p.first), m[p.second].insert(p.first); });
    	for (auto &p : points)
    		if (m[p.second].count(x_min + x_max - p.first) == 0)
    			return false;
    	return true;
    }
    

Log in to reply
 

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