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.

Solution

public class Solution {

    public boolean isReflected(int[][] points) {
        if(points.length == 0) return true;
        int minX = points[0][0];
        int maxX = points[0][0];
        Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
        for(int i = 0; i < points.length; i++) {
            minX = Integer.min(minX, points[i][0]);
            maxX = Integer.max(maxX, points[i][0]);

            int X = points[i][0];
            int Y = points[i][1];
            if(!map.containsKey(X)) map.put(X, new HashMap<Integer,Integer>());
            if(!map.get(X).containsKey(Y)) map.get(X).put(Y, 1);
        }

        long middle = (long) minX + maxX;
        Set<Integer> checked = new HashSet<Integer>();
        for(Integer X: map.keySet()) {
            if(!checked.add(X)) continue;
            checked.add((int)(middle-X));

            Map<Integer, Integer> map1 = map.get(X);
            Map<Integer, Integer> map2 = map.get((int)(middle-X));
            if(map2 == null) return false;
            for(Integer Y: map1.keySet()) {
                if(!map2.containsKey(Y)) {
                    return false;
                }
            }
        }
        return true;
    }
}