Skip to main content
Talentd

Line Reflection - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableMath4 min readAsked at: Google, Yandex
Practice this problem

Problem Statement

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 <= 104
  • -108 <= points[i][j] <= 108

 

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

Approach Overview

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(n2), 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(n2) 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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise Reflection Check (Brute Force)O(n^2)O(1)Useful for understanding the reflection concept or when constraints are very small
Hash Set with Min/Max Reflection LineO(n)O(n)General optimal solution with fast lookups for mirrored points

Video Solution

Line Reflection || Leetcode • Pepcoding • 4,177 views views

Watch 7 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Line Reflection with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Points on a Line

Next

Number of Boomerangs