356. Line Reflection

Line Reflection

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given 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)?

Credits:Special thanks to @memoryless for adding this problem and creating all test cases.

Solution

public class Solution {
    public boolean isReflected(int[][] points) {
        if (points == null || points.length == 0) return true;

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        Set<String> set = new HashSet<>();
        for (int i = 0; i < points.length; i++) {
            min = Math.min(min, points[i][0]);
            max = Math.max(max, points[i][0]);
            set.add(points[i][0] + "a" + points[i][1]);
        }

        int sum = min + max;
        for (int i = 0; i < points.length; i++) {
            int[] point = points[i];

            String reflectPoint = (sum - point[0]) + "a" + point[1];
            if (!set.contains(reflectPoint)) {
                return false;
            }
        }

        return true;
    }
}