AC Java with explain from hint, not using average


  • 1
    D

    Thanks for StefanPochmann's test case. I found that average solution does not work for odd points. As the example StefanPochmann provided [[0,0],[1,0],[3,0]]. There is no reflection line. With average code, it returns true.

    So after read the hint and StefanPochmann's solution, I made it with Java.

    Just sort the points with x. Then "reflect" it by assume there is a x-axis formed by min_x and max_x. Then resorted the array. All the points should be same as the first sort.

    public class Solution {
        public boolean isReflected(int[][] points) {
        if (points == null) {
            return false;
        }
        
        Arrays.sort(points, new ArrComparator());
        
        int[][] reflectedPoints = new int[points.length][2];
        for (int i = 0; i < reflectedPoints.length; i++) {
            reflectedPoints[i][0] = points[0][0] + points[reflectedPoints.length-1][0] - points[i][0];
            reflectedPoints[i][1] = points[i][1];
        }
        
        Arrays.sort(reflectedPoints, new ArrComparator());
        
        for (int i = 0; i < reflectedPoints.length; i++) {
            if (reflectedPoints[i][0] != points[i][0] ||
                reflectedPoints[i][1] != points[i][1]) {
                    return false;
                }
        }
        return true;
    }
    
    public class ArrComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] a, int b[]) {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        }
    }
    

    }


    ------------------------------FOLLOWING SOLUTION DOES NOT WORK-----------------

    The approach is pretty simple the line has been restricted to be parallel to y axis. So we can just simply find the average of each y coordinate, which is the potential reflection x-axis.

    Then just check whether all the reflection x-axis are same or not.

    public class Solution {
      public boolean isReflected(int[][] points) {
        if (points == null) {
            return false;
        }
        
        Map<Integer, List<Double>> aggregated = new HashMap<>();
        for (int[] point : points) {
            // First number for how many number are counted, second is the x average.
            if (!aggregated.containsKey(point[1])) {
                aggregated.put(point[1], new ArrayList<>(2));
                aggregated.get(point[1]).add(0, 1.0);
                aggregated.get(point[1]).add(1, (double)point[0]);
            } else {
                double prevCount = aggregated.get(point[1]).get(0);
                aggregated.get(point[1]).set(0, prevCount + 1);
                aggregated.get(point[1]).set(1, (aggregated.get(point[1]).get(1) * prevCount + point[0]) / ++prevCount);
            }
        }
        
        // Check potential x - axis are same or not.
        Double prev = null;
        for (List<Double> data : aggregated.values()) {
            if (prev != null && !data.get(1).equals(prev)) {
                return false;
            }
            prev = data.get(1);
        }
        return true;
    }
    

    }


  • 2

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


  • 0
    D

    Thanks! I think this solution does not work......


Log in to reply
 

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