Java 2 pass solution with a math theory behind.


  • 0
    V

    There are primarily 2 properties that needs to be satisfied for reflection.

    1. Every point must have reflection.
    2. They must reflect over one line (that line would be passing through the mid point of maxX and minX).

    => let us consider x = k is the line that passes through the mid point.
    k = (minX + maxX) / 2 --> (1)

    => Now, consider two arbitrary points that reflect onto each other let us consider them as x1 and x2, we have the following
    k - x1 = x2 - k => 2k = x1 + x2 ->(2)

    from (1) and (2), we have x1 + x2 = minX + maxX (which is what we use in this algorithm).

    I got the math logic, still I failed to get the intuitive idea/thought process behind minX + maxX = x1 + x2, can anyone please illuminate me ?

    class Solution {
        public boolean isReflected(int[][] points) {
            Set<String> set = new HashSet<>();
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int[] p : points) {
                min = Math.min(min, p[0]);
                max = Math.max(max, p[0]);
                String key = p[0] + "#" + p[1];
                set.add(key);
            }
            
            int sum = min + max;
            for(int[] p : points) {
                String key = (sum - p[0]) + "#" + p[1];
                if (!set.contains(key)) return false;
            }
            
            return true;
            
        }
    }
    

Log in to reply
 

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