Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/356.html

Given n points on a 2D plane, find if there is such a line parallel to the y-axis that reflects 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 original points' set is the same as the reflected ones.

Note that there can be repeated points.

 

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 <= 104
• -108 <= points[i][j] <= 108

 

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

Algorithm

The hints in the question are quite adequate, we just need to follow the hinted steps to solve the problem.

• First, we find the maximum and minimum values of the abscissa of all points, then the average of the two is the abscissa of the middle straight line,
• Then we traverse each point, and if we can find another point that is symmetrical in a straight line, we return true, otherwise we return false

Code

• Java
• Python

• import java.nio.ByteBuffer;
  import java.util.HashSet;
  import java.util.Set;
  
  public class Line_Reflection {
  
      class Solution {
          public boolean isReflected(int[][] points) {
              if (points.length <= 1) {
                  return true;
              }
  
              int min = Integer.MAX_VALUE;
              int max = Integer.MIN_VALUE;
              Set<Long> pointSet = new HashSet<>();
              for(int[] p: points) {
                  min = Math.min(min, p[0]);
                  max = Math.max(max, p[0]);
                  pointSet.add(pointToLong(p[0], p[1])); // overflow
              }
  
              int sum = min + max;
              for(int[] p: points) {
                  if(!pointSet.contains(pointToLong(sum - p[0], p[1])))
                      return false;
              }
              return true;
          }
  
          public long pointToLong(int x, int y) {
              ByteBuffer bb = ByteBuffer.allocate(8);
              bb.putInt(x);
              bb.putInt(y);
              return bb.getLong(0);
          }
      }
  
  }
  
  ############
  
  class Solution {
      public boolean isReflected(int[][] points) {
          int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
          Set<String> pointSet = new HashSet<>();
          for (int[] point : points) {
              minX = Math.min(minX, point[0]);
              maxX = Math.max(maxX, point[0]);
              pointSet.add(point[0] + "." + point[1]);
          }
          long s = minX + maxX;
          for (int[] point : points) {
              if (!pointSet.contains((s - point[0]) + "." + point[1])) {
                  return false;
              }
          }
          return true;
      }
  }
  

• class Solution:
      def isReflected(self, points: List[List[int]]) -> bool:
          min_x, max_x = inf, -inf
          point_set = set()
          for x, y in points:
              min_x = min(min_x, x)
              max_x = max(max_x, x)
              point_set.add((x, y))
          s = min_x + max_x
          for x, y in points:
              if (s - x, y) not in point_set:
                  return False
          return True
  
  ############
  
  class Solution(object):
    def isReflected(self, points):
      """
      :type points: List[List[int]]
      :rtype: bool
      """
      if len(points) < 2:
        return True
      twoTimesMid = min(points)[0] + max(points)[0]
      d = set([(i, j) for i, j in points])
      for i, j in points:
        if (twoTimesMid - i, j) not in d:
          return False
      return True
  
  

All Problems

All Solutions