Line Reflection - Solution & Explanation

Problem Overview: You are given a list of 2D points on a plane. The task is to determine whether there exists a vertical line such that every point has its mirror reflection across that line within the same set of points.

Approach 1: Pairwise Reflection Check (Brute Force) (Time: O(n²), Space: O(1))

A direct way is to test whether a possible reflection line works for all points. One candidate line can be derived from the average of two points' x-coordinates. For each candidate line x = c, iterate through all points and verify that their mirrored coordinate (2c - x, y) exists somewhere in the list. Because checking existence requires scanning the array, each lookup costs O(n). This leads to O(n²) time in the worst case. The approach uses constant extra memory but becomes slow as the number of points grows.

Approach 2: Hash Set with Min/Max Reflection Line (Optimal) (Time: O(n), Space: O(n))

The key observation: if a vertical reflection line exists, it must lie exactly halfway between the smallest and largest x-coordinates in the set. Compute minX and maxX by iterating once through the points. The potential reflection line becomes x = (minX + maxX) / 2. Store all points in a hash set using a string or tuple representation like (x, y).

Now iterate through each point again. For a point (x, y), its mirrored partner across the line must be (minX + maxX - x, y). Perform a constant-time hash lookup to confirm the mirrored point exists. If any reflected point is missing, symmetry fails immediately. If all points pass the check, the set is symmetric across the computed line.

This approach leverages a hash table for O(1) lookups and uses a simple math observation about reflection. The input is processed with linear scans of the array, giving O(n) time complexity and O(n) additional space for the set.

Recommended for interviews: The hash-set reflection approach is the expected solution. It shows that you recognize the geometric property of the reflection line and can combine it with constant-time membership checks. Mentioning the brute-force idea first demonstrates understanding of the symmetry requirement, but implementing the O(n) hash-based method shows stronger algorithmic reasoning.