356. Line Reflection

I followed the hit and solved the problem by set.

1:  class Solution {  
2:  public:  
3:    bool isReflected(vector<pair<int, int>>& points) {  
4:      set<pair<int,int>> s;  
5:      int minX = INT_MAX, maxX = INT_MIN;  
6:      for (int i = 0; i < points.size(); i++) {  
7:        minX = min(points[i].first, minX);  
8:        maxX = max(points[i].first, maxX);  
9:        s.insert(points[i]);  
10:      }  
11:      double y = (minX + maxX) * 1.0 / 2;  
12:      for (int i = 0; i < points.size(); i++) {  
13:        if (!s.count(make_pair(2*y-points[i].first, points[i].second))) return false;  
14:      }  
15:      return true;  
16:    }  
17:  };  

Obviously, this code can be improved because for line 12 we don't have to traverse all points. We can use unordered_map and y as key and the set of its corresponding x's as value. For each y, we traverse from two ends of the set (note numbers in set is sorted). This solution is faster than the first one.

1:  class Solution {  
2:  public:  
3:    bool isReflected(vector<pair<int, int>>& points) {  
4:      unordered_map<int, set<int>> mp;  
5:      int minX = INT_MAX, maxX = INT_MIN;  
6:      for (int i = 0; i < points.size(); i++) {  
7:        minX = min(points[i].first, minX);  
8:        maxX = max(points[i].first, maxX);  
9:        mp[points[i].second].insert(points[i].first);  
10:      }  
11:      double y = (minX + maxX) * 1.0 / 2;  
12:      for (auto i : mp) {  
13:        set<int> tmp = i.second;  
14:        for (auto start = tmp.begin(), end = tmp.end(); start != end; start++) {  
15:          if ((*start + *--end) / 2.0 != y) return false;  
16:          if (start == end) break;  
17:        }  
18:      }  
19:      return true;  
20:    }  
21:  };