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

• 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;
}``````

• 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.

• 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;
}
``````

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