Monday, October 17, 2016

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

According to hint, we can find the maximum and minimum x coordinate for all points. The sum of x_min and x_max should be the sum for all reflected points. Now we check for every point, if sum - p[0] exists. If not, return false.


public boolean isReflected(int[][] points) {
        Map<integer, <integer, set,>> pointsMap = new HashMap<>();
        int minx = Integer.MAX_VALUE, maxx = Integer.MIN_VALUE;
        for (int[] p : points) {
            if (!pointsMap.containsKey(p[1])) {
                pointsMap.put(p[1], new HashSet<>());
            }
            pointsMap.get(p[1]).add(p[0]);
            minx = Math.min(p[0], minx);
            maxx = Math.max(p[0], maxx);
        }
        int sum = minx + maxx;
        for (int[] p : points) {
            if (!pointsMap.containsKey(p[1])) {
                return false;
            }
            Set<integer> xs = pointsMap.get(p[1]);
            if (!xs.contains(sum - p[0])) {
                return false;
            }
            xs.remove(sum - p[0]);
            if (xs.size() == 0) {
                pointsMap.remove(p[0]);
            }
        }
        return true;
    }


No comments:

Post a Comment