Leetcode 356. Line Reflection

Problem Explanation:

Given 'n' number of points in a 2-Dimensional plane, we are to determine if there a line parallel to the y-axis that reflects the given points. We can start off by initializing two variables (minX and maxX) to keep track of the minimum 'x' coordinate and maximum 'x' coordinate value. Next, we traverse the array by comparing the 'x' coordinate of each list to both min 'x' and max 'x' in order to update their value.

After obtaining the minimum 'x' and maximum 'x' values, we can calculate a sum of both the minimum 'x' and maximum 'x' value. If there is a point such that it is not in the hash set with an 'x' coordinate of (minX + maxX - current x) and a 'y' coordinate of (current y), we would return false else true.

Walkthrough:

Consider an example with the following points [[1,1],[-1,1]]. The minimum x-coordinate is -1 and the maximum x-coordinate is 1 therefore the sum of minX and maxX is 0. Both points are in a hashset and, when we subtract their x-coordinate from the sum (0), the result is in the hashset. Thus, there is a line parallel to the y-axis that reflects the points.

Coding Solution:

1
2python 
3class Solution:
4    def isReflected(self, points):
5        xs = [x for x, _ in points]
6        minx, maxx = min(xs), max(xs)
7        sumx = minx + maxx
8        points_set = {(x, y) for x, y in points}
9        for x, y in points:
10            if (sumx - x, y) not in points_set:
11                return False
12        return True

1
2java
3class Solution {
4    public boolean isReflected(int[][] points) {
5        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
6        HashSet<String> set = new HashSet<>();
7        for(int[] p:points){
8            min = Math.min(min,p[0]);
9            max = Math.max(max,p[0]);
10            String str = p[0] + "a" + p[1];
11            set.add(str);
12        }
13        int sum = min+max;
14        for(int[] p:points){
15            //int[] arr = {sum-p[0],p[1]};
16            String str = (sum-p[0]) + "a" + p[1];
17            if( !set.contains(str)) return false;
18
19        }
20        return true;
21    }
22}

1
2javascript 
3class Solution {
4    isReflected(points) {
5        let min = Number.MAX_SAFE_INTEGER, max = Number.MIN_SAFE_INTEGER;
6        let set = new Set();
7        for (let [x, y] of points) {
8            min = Math.min(min, x);
9            max = Math.max(max, x);
10            set.add(x + "a" + y);
11        }
12        let sum = min + max;
13        for (let [x, y] of points) {
14            if (!set.has(sum - x + "a" + y)) return false;
15        }
16        return true;
17    }
18}

1
2cpp
3struct pairHash {
4    template <class T1, class T2>
5    std::size_t operator () (std::pair<T1,T2> const &pair) const
6    {
7        std::size_t h1 = std::hash<T1>()(pair.first);
8        std::size_t h2 = std::hash<T2>()(pair.second);
9
10        return h1 ^ h2;
11    }
12};
13
14class Solution {
15public:
16    bool isReflected(vector<pair<int, int>>& points) {
17        int MIN = INT_MAX, MAX = INT_MIN;
18        unordered_set<pair<int, int>, pairHash> s;
19        for (auto p : points) {
20            MIN = min(MIN, p.first);
21            MAX = max(MAX, p.first);
22            s.insert(p);
23        }
24        int sum = MIN + MAX;
25        for (auto p : points) {
26            if (!s.count(make_pair(sum - p.first, p.second)))
27                return false;
28        }
29        return true;
30    }
31};

1
2csharp
3public class Solution {
4    public bool IsReflected(int[][] points) {
5        if(points == null || points.Length == 0)
6        {
7            return true;
8        }
9        
10        HashSet<string> uniquePoints = new HashSet<string>();
11        int maxX = int.MinValue;
12        int minX = int.MaxValue;
13        foreach(var point in points)
14        {
15            maxX = Math.Max(maxX, point[0]);
16            minX = Math.Min(minX, point[0]);
17            uniquePoints.Add($"{point[0]}:{point[1]}");
18        }
19        
20        int total = maxX + minX;
21        
22        foreach(var point in points)
23        {
24            var antiPoint = new int[2]{ total - point[0], point[1] };
25            if(!uniquePoints.Contains($"{antiPoint[0]}:{antiPoint[1]}"))
26            {
27                return false;
28            }
29        }
30
31        return true;
32    }
33}

Explanation of Coding Solution:

The code solution given for Python, Java, Javascript, C++ and C# all follow the same logic with minor differences in implementation due to the differences in the languages themselves.

We first initialize two variables to keep track of the minimum and maximum 'x' values (minX and maxX). The initial values of these are set as the maximum and minimum values a variable can hold in their respective languages. This is to ensure any point can update these initial values. In the case of Python, max and min functions are used to extract min and max 'x' value from the list of points.

We also initialize a unique set of points which will store the string representation of each point. Using a HashSet ensures the quick retrieval of elements and checking of existence, which has a time complexity of O(1).

Then we iterate over the points. At each iteration we add all the points to the set and simultaneously we keep updating minX and maxX to represent the minimum 'x' and maximum 'x' values encountered respectively which are extracted from the points under consideration.

Afterwards, we calculate total, which is the sum of minX and maxX.

Last, we iterate over the points again to check for each point, whether its reflection with respect to the line x = total/2 exists. The reflection of the point (x,y) with respect to the line, x = total /2 , will be (total - x, y). If there is any point whose reflection is not in the list, then we return false. If reflections of all the points are found in the list, then we return true.

In this way, the given solution checks if a mirror-line exists which can reflect all given points on the 2D plane. This solution uses a HashSet to store points and minimize the checking of existence of a point. The time complexity of this solution is O(n) where n is the number of points given, as we are iterating over all points twice. The space complexity is also O(n) for storing points in the set for checking later. This implementation is efficient and adequately answers the given problem.