Line Reflection solution and explanation
Google
7 more videos on this problem
Line Reflection || LeetcodePepcoding · 18:33 · 4K views
356. Line Reflection (Leetcode Medium)Programming Live with Larry · 12:57 · 3K views
Yandex Interview Question - Line Reflection- Leetcode 356- PythonSephorus · 8:22 · 2K views
Leetcode Problem Line Reflection [ English ]Bevanthe's Code Studio · 16:21 · 853 views
Line Reflection, LeetCode Medium, C++H William Polenz · 47:03 · 427 views
356. Line ReflectionLeetcode and Interview Question · 10:11 · 152 views
LeetCode 356. Line ReflectionYuki Kitayama · 47:25 · 150 views
LeetCode 356: Line ReflectionAlitaCode · 25:42 · 53 views
The problem
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.length1 <= 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
class Solution:
def isReflected(self, points: List[List[int]]) -> bool:
min_x, max_x = inf, -inf
point_set = set()
for x, y in points:
min_x = min(min_x, x)
max_x = max(max_x, x)
point_set.add((x, y))
s = min_x + max_x
return all((s - x, y) in point_set for x, y in points)class Solution {
public boolean isReflected(int[][] points) {
final int inf = 1 << 30;
int minX = inf, maxX = -inf;
Set<List<Integer>> pointSet = new HashSet<>();
for (int[] p : points) {
minX = Math.min(minX, p[0]);
maxX = Math.max(maxX, p[0]);
pointSet.add(List.of(p[0], p[1]));
}
int s = minX + maxX;
for (int[] p : points) {
if (!pointSet.contains(List.of(s - p[0], p[1]))) {
return false;
}
}
return true;
}
}class Solution {
public:
bool isReflected(vector<vector<int>>& points) {
const int inf = 1 << 30;
int minX = inf, maxX = -inf;
set<pair<int, int>> pointSet;
for (auto& p : points) {
minX = min(minX, p[0]);
maxX = max(maxX, p[0]);
pointSet.insert({p[0], p[1]});
}
int s = minX + maxX;
for (auto& p : points) {
if (!pointSet.count({s - p[0], p[1]})) {
return false;
}
}
return true;
}
};func isReflected(points [][]int) bool {
const inf = 1 << 30
minX, maxX := inf, -inf
pointSet := map[[2]int]bool{}
for _, p := range points {
minX = min(minX, p[0])
maxX = max(maxX, p[0])
pointSet[[2]int{p[0], p[1]}] = true
}
s := minX + maxX
for _, p := range points {
if !pointSet[[2]int{s - p[0], p[1]}] {
return false
}
}
return true
}Complexity analysis
| Approach | Time | Space | When 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 Line | O(n) | O(n) | General optimal solution with fast lookups for mirrored points |
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.