356 Line Reflection¶

Problem:¶

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

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.

Solutions:¶

public class Solution {
    public boolean isReflected(int[][] points) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        HashMap<Integer, HashSet<Integer>> ys = new HashMap<Integer, HashSet<Integer>>();
        for (int i = 0; i < points.length; i ++) {
            int x = points[i][0];
            int y = points[i][1];
            min = Math.min(min, x);
            max = Math.max(max, x);
            if (!ys.containsKey(x)) {
                ys.put(x, new HashSet<Integer>());
            }
            ys.get(x).add(y);
        }
        int doublebar = (min + max);
        for (int i = 0; i < points.length; i ++) {
            int x = points[i][0];
            int y = points[i][1];
            int mx = doublebar - x;
            if (!ys.containsKey(mx)) {
                return false;
            }
            if (!ys.get(mx).contains(y)) {
                return false;
            }
        }

        return true;
    }
}

class Solution {
    public boolean isReflected(int[][] points) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        HashMap<Integer, HashSet<Integer>> ys = new HashMap<Integer, HashSet<Integer>>();
        for (int i = 0; i < points.length; i ++) {
            int x = points[i][0];
            int y = points[i][1];
            min = Math.min(min, x);
            max = Math.max(max, x);
            if (!ys.containsKey(y)) {
                ys.put(y, new HashSet<Integer>());
            }
            ys.get(y).add(x);
        }
        int doublebar = (min + max);
        for (Integer y:ys.keySet()) {
            for (Integer x:ys.get(y)) {
                int mx = doublebar - x;
                if (!ys.get(y).contains(mx)) {
                    return false;
                }
            }
        }
        return true;
    }
}