Is Line Reflection easy or hard?

Line Reflection is generally classified as a medium-level problem. The implementation is simple once you identify the correct reflection line, but many candidates initially miss the minX + maxX insight that reduces the problem to O(n).

Line Reflection Python/Java solution

The typical implementation stores points in a set of tuples (Python) or encoded strings/objects (Java). After computing minX and maxX, iterate through each point and check whether (minX + maxX - x, y) exists in the set. The same logic works in C++, Go, and other languages with hash-based containers.

How to solve Line Reflection in O(n)?

Compute minX and maxX from the points to determine the only possible reflection line. Insert every point into a hash set. For each point (x, y), check whether the mirrored point (minX + maxX - x, y) exists in the set. If all reflections exist, the points form a valid symmetric set across the vertical line.

What is the best approach for Line Reflection?

The optimal approach uses a hash set combined with a geometric observation. First compute the smallest and largest x-coordinates, which define the only possible reflection line x = (minX + maxX) / 2. Then store all points in a hash set and verify that every point (x, y) has its mirrored partner (minX + maxX - x, y). This runs in O(n) time with O(n) space.

Is Line Reflection asked at Google/Amazon/Meta?

Line Reflection appears in interview preparation lists for companies that test geometry and hash table reasoning, including Google and Meta-style interview question sets. The problem evaluates whether candidates can combine a math insight with efficient data structure usage.

What data structure is used in Line Reflection?

A hash set is the main data structure used in the optimal solution. It stores each point so mirrored coordinates can be checked in constant time. Arrays are used for the input points, and a simple math calculation determines the reflection line.

What is the time complexity of Line Reflection?

The optimal solution runs in O(n) time because the algorithm scans the list of points a few times and uses O(1) hash lookups for reflection checks. Space complexity is O(n) due to storing all points in a hash set for fast membership testing.

356. Line Reflection - Practice Online

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

In other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points' set is the same as the reflected ones.

Note that there can be repeated points.

Example 1:

Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.

Example 2:

Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.

Constraints:

n == points.length
1 <= n <= 10⁴
-10⁸ <= points[i][j] <= 10⁸

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