Question

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

 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)?

 Hint:
     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.

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

356 - Line Reflection

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions