Solution and Explanation


  • 0
    L

    My first approach to solve this problem was to sort all points by its x-coordinates, find the mid point of all points and then use 2-pointer to iterate through the sorted points from both side, and check if they are symmetric.

    It turn out this approach is a pain in the neck. Because sorting all points is not easy. The compare function used in sorting depends on where the middle line is. If you are not convinced, please think about how to compare 2 points that have the same x-coordinate.

    A more intuitive and easier to implement approach is to do the following. For each possible y-coordinate in the input:

    • Count the total number of points at that y-coordinate
    • Sum x-coordinate over all points at that y-coordinate

    We know that for each y-coordinate, all points at the same y-coordinate are symmetric (you can always find a line by taking the average of all x-coordinates). If at each y-coordinate, the average of x-coordinate are identical, then all points are symmetric to the same line.

    The average of x-coordinates may not be an integer, therefore don't use "==" to compare the result.

    public boolean isReflected(int[][] points) {
        // count the number of points on each possible horizontal line
        // calculate the average of x coordinate of each possible horizontal line
        // they should match
        
        Map<Integer, Integer> yCount = new HashMap<>();
        Map<Integer, Integer> ySum = new HashMap<>();
        int x;
        int y;
        for (int[] p : points) {
            x = p[0];
            y = p[1];
            if (!yCount.containsKey(y)) {
                yCount.put(y, 1);
                ySum.put(y, x);
            } else {
                yCount.put(y, yCount.get(y) + 1);
                ySum.put(y, ySum.get(y) + x);
            }
        }
        
        Double epsilon = 10E-9;
        Double avg = null;
        
        for (int key : yCount.keySet()) {
            if (avg == null) {
                avg = ySum.get(key) * 1.0 / yCount.get(key);
            } else if (Math.abs(avg - ySum.get(key) * 1.0 / yCount.get(key)) > epsilon) {
                return false;
            }
        }
        
        return true;
    }

  • 0

    Trivial to break, fails for example [[0,0],[1,0],[3,0]].


  • 0
    L

    Thank you Stefan.
    You are absolutely right.
    My code fails the test case [[0,0],[1,0],[3,0], [-2,1], [1,1], [5,1]] too.
    These cases should be added to the test cases.


  • 0
    L

    The above solution is wrong. I have closed the discussion.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.