Problem Description

The Line Reflection problem asks: Given a set of 2D points on the XY-plane, determine if there exists a vertical line (parallel to the Y-axis) such that each point in the set has a reflection about this line that is also in the set.

• Each point is represented as a pair [x, y].
• The reflection line must be vertical, i.e., have the form x = c for some constant c.
• All reflected points must also exist in the original set (no extra points allowed).
• Points may be duplicated in the input, but each must be matched by its reflection.

The task is to return true if such a line exists, and false otherwise.

Thought Process

At first glance, you might think of brute-forcing all possible vertical lines through the points and checking for each if all points are symmetric about it. However, this would be highly inefficient, especially for large inputs.

Instead, think about the properties of reflection:

• For a line x = c, the reflection of a point (x, y) is (2c - x, y).
• So, for each point, its reflection must also be a point in the set.
• To minimize work, we can focus on the smallest and largest x-coordinates. The "center" between them is a good candidate for the reflection line.

The challenge is to efficiently check that for every point, its mirror image about this line also exists in the set.

Solution Approach

Let's break the solution down step-by-step:

1. Find the reflection line candidate:
   • Find the minimum and maximum x values among all points: minX and maxX.
   • The only possible vertical reflection line is at x = (minX + maxX) / 2.
2. Store all points for quick lookup:
   • Put all points into a set (or hash map) so you can check existence in O(1) time.
3. Check for symmetry:
   • For each point (x, y), compute its reflected x-coordinate: xr = minX + maxX - x.
   • Check if (xr, y) exists in the set.
   • If any point fails this check, return false.
4. If all points pass, return true.

This approach is efficient because:

• It only checks one candidate line.
• It leverages fast set lookups for symmetry checks.

Example Walkthrough

Let's walk through an example:

    Input: points = [[1,1], [2,1], [3,1]]
  

• minX = 1, maxX = 3
• Reflection line: x = (1 + 3) / 2 = 2
• Check each point:
  • (1,1): reflection is (3,1) → exists
  • (2,1): reflection is (2,1) → exists
  • (3,1): reflection is (1,1) → exists
• All points have their reflections, so the answer is true.

If we had a point like (4,1), its reflection would be (0,1), which is not in the set, so the answer would be false.

Time and Space Complexity

• Brute-force approach:
  • Try every possible vertical line between each pair of points: O(N^2) lines.
  • For each line, check symmetry for all N points: O(N^3) total.
• Optimized approach (as above):
  • Finding minX and maxX: O(N).
  • Inserting all points into a set: O(N).
  • Checking symmetry for all points: O(N), each lookup O(1).
  • Total: O(N) time and O(N) space.

This is a significant improvement, making the solution efficient for large datasets.

Summary

The key insight is that the only possible reflection line is halfway between the smallest and largest x-coordinates. By leveraging a set for O(1) lookups and checking every point's reflection, we ensure correctness and efficiency. This solution is elegant because it turns a seemingly complex geometric problem into simple arithmetic and set operations, making it both fast and easy to understand.

Code Implementation

class Solution:
    def isReflected(self, points):
        point_set = set((x, y) for x, y in points)
        min_x = min(x for x, y in points)
        max_x = max(x for x, y in points)
        target = min_x + max_x
        for x, y in points:
            if (target - x, y) not in point_set:
                return False
        return True
    

class Solution {
public:
    bool isReflected(vector<vector<int>>& points) {
        unordered_set<string> pointSet;
        int minX = INT_MAX, maxX = INT_MIN;
        for (auto& p : points) {
            minX = min(minX, p[0]);
            maxX = max(maxX, p[0]);
            pointSet.insert(to_string(p[0]) + "," + to_string(p[1]));
        }
        int target = minX + maxX;
        for (auto& p : points) {
            int xr = target - p[0];
            string reflected = to_string(xr) + "," + to_string(p[1]);
            if (pointSet.find(reflected) == pointSet.end()) {
                return false;
            }
        }
        return true;
    }
};
    

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

var isReflected = function(points) {
    let pointSet = new Set();
    let minX = Infinity, maxX = -Infinity;
    for (let [x, y] of points) {
        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x);
        pointSet.add(x + ',' + y);
    }
    let target = minX + maxX;
    for (let [x, y] of points) {
        let xr = target - x;
        if (!pointSet.has(xr + ',' + y)) {
            return false;
        }
    }
    return true;
};