Formatted question description:

 356	Line Reflection

 Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given set of points.

 Example 1:
 Given points = [[1,1],[-1,1]], return true.

 Example 2:
 Given points = [[1,1],[-1,-1]], return false.

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

     Find the smallest and largest x-value for all points.
     If there is a line then it should be at y = (minX + maxX) / 2.
     For each point, make sure that it has a reflected point in the opposite side.


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



  • 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);
                return bb.getLong(0);
  • Todo
  • 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