NeetCode #938LC-356MediumMath & Geometry
← Back to All Problems#938 · #356 · Line Reflection(直线镜像)
📌 Problem Statement & Constraints
Given
n integer points points[i] = [xi, yi], determine whether a line parallel to the y-axis exists such that reflecting every point across it yields a point also in the set. Constraints: 1 <= n <= 10^4, -10^8 <= xi, yi <= 10^8.💡 Core Algorithmic Approaches
- If such a line
x = Lexists, it must be exactly midway between the leftmost and rightmost points, soL = (minX + maxX) / 2. - To avoid floating point, work with doubled coordinates: set
s = minX + maxX, so the reflection of(x, y)is(s - x, y). - Store all points in a hash set; the reflection must be present for every point.
- Return true only if every reflection is found.
💻 Benchmark Python3 Implementation
class Solution:
def isReflected(self, points: List[List[int]]) -> bool:
xs = [p[0] for p in points]
s = min(xs) + max(xs) # twice the axis x-coordinate
pts = set(map(tuple, points))
for x, y in points:
if (s - x, y) not in pts: # mirrored point must exist
return False
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): build the set and check every point.
💾 Space Complexity
O(n): the point set.
⚠️ Interview Pitfalls & Follow-ups
- Using a floating-point axis:
(minX + maxX) / 2can be a half-integer; doubled coordinates keep everything integral. - Checking only the x-coordinates: the mirrored point must also match in y.
- Thinking the axis might not be unique: the extreme points fix it uniquely.
- Skipping deduplication: duplicates do not change the answer, but a set makes lookups fast.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.