Solution For Line Reflection

The Line Reflection problem on LeetCode is a medium difficulty problem that requires you to check if a set of points can be reflected across a straight line. Here is a detailed solution for the problem:

Problem Statement

Given n points on a 2D plane, find if there exists a line such that the points can be reflected across the line.

You may assume that:

• There are at most 50 points.
• Each point given is an integer given in the range [-10^4, 10^4].
• A point is reflected across a line x = c as (c-x, y).

Solution Approach

The first step is to check whether there are at least two points provided. If there are less than two points, there won’t be any line to reflect across. If this is the case, we can simply return true.

Once we have established that there are at least two points available, we need to find the line of symmetry. If a line of symmetry exists, the midpoint of two points which are reflections of each other will lie on the line of symmetry.

We can find the midpoint of two points by taking the average of their x and y coordinates separately. Let’s call the midpoint coordinates as (mx, my).

Now, if a line of symmetry exists, for any two points (x1, y1) and (x2, y2) such that (x2 – x1, y2 – y1), their reflection coordinates will be (2 * mx – x1, 2 * my – y1), and (2 * mx – x2, 2 * my – y2), respectively.

We can sort all the points lexicographically and check whether all the pairs of points have their reflections lying on the line of symmetry.

Pseudo-code

The following is the pseudo-code to solve this problem:

1. Check whether the length of the points list is less than 2, return true if yes.
2. Find the midpoint of any two points in the list.
3. For all pairs of points (p1, p2) with p2 > p1:
4. Find their reflection coordinates (rx1, ry1) and (rx2, ry2).
5. If any of the reflection coordinates do not fall on the line of symmetry, return false.
6. Return true if all points have been reflected across the line of symmetry.

Time and Space Complexity

The time complexity of this algorithm is O(n log n) since we have to sort the points. The space complexity is O(n) because we are storing the points in a list.

Conclusion

The line reflection problem on Leetcode requires you to find whether a set of points can be reflected across a straight line. The approach involves identifying a line of symmetry and reflecting each pair of points around that line. This problem can be solved efficiently with O(n log n) time and O(n) space complexity.

Step by Step Implementation For Line Reflection

/*

We can solve this problem by first finding the point of reflection, and then checking if each point is reflected across that line.

To find the point of reflection, we can take the average of the x-coordinates of the two most extreme points. This will be the x-coordinate of the point of reflection. We can do the same for the y-coordinates.

Once we have the point of reflection, we can check if each point is reflected across that line. To do this, we can simply check if the point's x-coordinate is equal to the reflection's x-coordinate, and if the point's y-coordinate is equal to the reflection's y-coordinate.

*/

public boolean isReflected(int[][] points) {
    
    // find the point of reflection
    int x1 = points[0][0];
    int x2 = points[0][0];
    int y1 = points[0][1];
    int y2 = points[0][1];
    
    for (int[] point : points) {
        x1 = Math.min(x1, point[0]);
        x2 = Math.max(x2, point[0]);
        y1 = Math.min(y1, point[1]);
        y2 = Math.max(y2, point[1]);
    }
    
    int xReflection = x1 + (x2 - x1) / 2;
    int yReflection = y1 + (y2 - y1) / 2;
    
    // check if each point is reflected across the line of reflection
    for (int[] point : points) {
        if (point[0] != xReflection || point[1] != yReflection) {
            if (point[0] != 2 * xReflection - point[0] || point[1] != 2 * yReflection - point[1]) {
                return false;
            }
        }
    }
    
    return true;
    
}

class Solution:
    def isReflected(self, points):
        """
        :type points: List[List[int]]
        :rtype: bool
        """
        
        # get the max and min x values
        x_vals = [x for x, y in points]
        min_x = min(x_vals)
        max_x = max(x_vals)
        
        # get the line of reflection
        line_of_reflection = min_x + max_x
        
        # create a set of tuples for the points
        point_set = set()
        for x, y in points:
            point_set.add((x, y))
        
        # check if the reflection of each point exists in the set
        for x, y in points:
            reflection_x = line_of_reflection - x
            if (reflection_x, y) not in point_set:
                return False
        
        return True

//Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points. 

//Example 1:
//Given points = [[1,1],[-1,1]], return true.

//Example 2:
//Given points = [[1,1],[-1,-1]], return false.

//Follow up:
//Could you do better than O(n2)?

var lineReflection = function(points) {
    
};

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.

Example 1:
Given points = [[1,1],[-1,1]], return true.

Example 2:
Given points = [[1,1],[-1,-1]], return false.

Follow up:
Could you do better than O(n2)?

Hint:

Find the smallest and largest x-value for all points.
If there is a line then it should be at y = (minX + maxX) / 2.
For each point, make sure that it has a reflected point in the opposite side.

class Solution {
public:
    bool isReflected(vector>& points) {
        int n = points.size();
        if (n <= 1) return true;
        int minX = INT_MAX, maxX = INT_MIN;
        unordered_map> m;
        for (auto p : points) {
            m[p.second].insert(p.first);
            minX = min(minX, p.first);
            maxX = max(maxX, p.first);
        }
        int sum = minX + maxX;
        for (auto p : points) {
            int t = sum - p.first;
            if (!m.count(p.second) || !m[p.second].count(t)) return false;
        }
        return true;
    }
};

public class Solution {
    public bool IsReflected(int[][] points) {
        if (points == null || points.Length == 0) {
            return true;
        }
        int min = int.MaxValue;
        int max = int.MinValue;
        HashSet set = new HashSet();
        foreach (int[] point in points) {
            min = Math.Min(min, point[0]);
            max = Math.Max(max, point[0]);
            string key = point[0] + "a" + point[1];
            set.Add(key);
        }
        int sum = min + max;
        foreach (int[] point in points) {
            //int[] reflectedPoint = {sum - point[0], point[1]};
            string key = (sum - point[0]) + "a" + point[1];
            if (!set.Contains(key)) {
                return false;
            }
        }
        return true;
    }
}