⚡Flashcard Drill➔
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

  1. If such a line x = L exists, it must be exactly midway between the leftmost and rightmost points, so L = (minX + maxX) / 2.
  2. To avoid floating point, work with doubled coordinates: set s = minX + maxX, so the reflection of (x, y) is (s - x, y).
  3. Store all points in a hash set; the reflection must be present for every point.
  4. 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) / 2 can 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems