Line Reflection — Leetcode problem 356

Original Leetcode problem: https://leetcode.com/problems/line-reflection/

In this problem, we’re given a set of points and asked if it is true that all points can be reflected symmetrically across some line parallel to the y-axis.

A more straightforward solution would have been to use set.contains, but if you want to practice binary search, this is a good problem to do :)

My line of thought was to remove duplicate points, sort the array of points by x (and if x’s are equal, by y), then do binary search on each point left of the center which is calculated by taking the average of the (non-duplicate points’) x’s.

class Solution {
    
    class PointComparator implements Comparator<int[]> {
        public int compare(int[] p1, int[] p2) {
            if (p1[0] == p2[0]) {
                return Integer.compare(p1[1], p2[1]);
            }
            return Integer.compare(p1[0], p2[0]);
        }
    }
    
    public boolean isReflected(int[][] points) {
        if (points.length == 1) {
            return true;
        }
        Set<Pair<Integer, Integer>> set = new HashSet<>();
        int sum = 0;
        for (int[] p : points) {
            Pair<Integer, Integer> next = new Pair(p[0], p[1]);
            if (!set.contains(next)) {
                set.add(next);
                sum += p[0];
            }
        }
        double center = (double)sum / set.size();
        Set<int[]> arraySet = new HashSet<>();
        for (Pair<Integer, Integer> p : set) {
            arraySet.add(new int[]{p.getKey(), p.getValue()});
        }
        List<int[]> pointsList = new ArrayList<>(arraySet);
        Collections.sort(pointsList, new PointComparator());
        int n = pointsList.size();
        if (pointsList.get(0)[0] == pointsList.get(n - 1)[0]) {
            // all points in same y axis
            return true;
        }
        for (int i = 0; i < (n/2); i++) {
            // binary search for the corresponding point, if not found return false
            int[] point = pointsList.get(i);
            int reflected = (int)(center + (center - point[0]));
            boolean found = false;
            int left = n / 2;
            int right = n;
            while (left < right) {
                int mid = (left + right) / 2;
                int[] curr = pointsList.get(mid);
                
                if (curr[0] == center) {
                    // it's on the center so no need to check y coordinate
                    found = true;
                    break;
                } else if (curr[0] == reflected && curr[1] == point[1]) {
                    found = true;
                    break;
                } else if (curr[0] < reflected || (curr[0] == reflected && curr[1] < point[1])) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (!found) {
                return false;
            }
        }
        return true;
    }
}

The runtime and memory usage are fairly reasonable, though it varies depending on the leetcode server speed at the moment.