LeetCode [356] Line Reflection

356. Line Reflection

Medium

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points symmetrically, in other words, answer whether or not if there exists a line that after reflecting all points over the given line the set of the original points is the same that the reflected ones.

Note that there can be repeated points.

Follow up:
Could you do better than O(n2) ?

 

Example 1:

Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.

Example 2:

Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.

 

Constraints:

• n == points.length
• 1 <= n <= 10^4
• -10^8 <= points[i][j] <= 10^8

//C++
class Solution {
public:
  bool isReflected(vector<pair<int, int>>& points) {
    set<pair<int, int>> s;
    int maxX = INT_MIN;
    int minX = INT_MAX;
    for (auto p : points) {
      maxX = max(maxX, p.first);
      minX = min(minX, p.first);
      s.insert(p);
    }
    for (auto p : points) {
      int x = maxX - p.first + minX;
      if (!s.count(make_pair(x, p.second))) return false;
    }
    return true;
  }

};

//Java
class Solution {
    public boolean isReflected(int[][] points) {
        Set<String> pointset = new HashSet<String>();
        int maxX = Integer.MIN_VALUE;
        int minX = Integer.MAX_VALUE;
        for(int[] p : points){
            maxX = Math.max(maxX, p[0]);
            minX = Math.min(minX, p[0]);
            pointset.add(p[0]+":"+p[1]);
        }
        
        for(int[] p : points){
            int x = p[0], y = p[1];
            int x1 = maxX+minX-x;
            String p1 = x1+":"+y;
            if(!pointset.contains(p1)) return false;
        }
        
        return true;
    }
}