Java Sort + O(1) Space (8ms -- Beats 97.60%)


  • 0

    The tricky part is that you need to sort the points with same x according to their y.
    And you need to find the axis first. (if x <= axis, y in ascending order; if x > axis, y in decreasing order).
    Then in while loop, you need to jump the identical points as well as points on the axis.

    public class Solution {
        public boolean isReflected(int[][] points) {
            if (points == null || points.length == 0) {
                return true;
            }
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int[] point : points) {
                min = Math.min(min, point[0]);
                max = Math.max(max, point[0]);
            }
            double axis = min + (double) (max - min) / 2;
            Arrays.sort(points, new Comparator<int[]>() {
                public int compare(int[] point1, int[] point2) {
                    if (point1[0] == point2[0]) {
                        if (point1[0] <= axis) {
                           return point1[1] - point2[1]; 
                        } else {
                            return point2[1] - point1[1]; 
                        }
                    }
                    return point1[0] - point2[0];
                }
            });
            
            int left = 0;
            int right = points.length - 1;
            while (left <= right) {
                while (left < right && (points[left][0] == axis || isSame(points[left], points[left + 1]))) {
                    left++;
                }
                while (left < right && (points[right][0] == axis || isSame(points[right], points[right - 1]))) {
                    right--;
                }
                if (!isReflectedTwo(axis, points[left], points[right])) {
                    return false;
                }
                left++;
                right--;
            }
            
            return true;
        }
        
        private boolean isSame(int[] point1, int[] point2) {
            return point1[0] == point2[0] && point1[1] == point2[1];
        }
        
        private boolean isReflectedTwo(double axis, int[] point1, int[] point2) {
            if (point1[1] != point2[1]) {
                return false;
            }
            if (point1[0] - axis != axis - point2[0]) {
                return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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