LeetCode 356: Line Reflection Solution in Python – A Step-by-Step Guide

What Is LeetCode 356: Line Reflection?

In LeetCode 356: Line Reflection, you’re given an array points, where points[i] = [x_i, y_i] represents a point’s coordinates on a 2D plane. Your task is to determine if there exists a vertical line (x = constant) such that reflecting all points over it results in the same set of points. Reflection over a line x = m means for a point (x, y), its reflection is (2m - x, y). For example, with points = [[1,1], [-1,1]], reflecting over x = 0 maps 1 to -1 and -1 to 1, matching the set, so the answer is True.

Problem Statement

• Input: An array points of integer pairs [x_i, y_i].
• Output: A boolean—True if a reflection line exists, False otherwise.
• Rules:
• Reflection is over a vertical line (x = m).
• Reflected point: (x, y) → (2m - x, y).
• All points must have a matching reflection in the set.
• Points can overlap (e.g., multiple at same coordinates).

Constraints

• 1 <= points.length <= 10⁴
• points[i].length == 2
• -10⁸ <= x_i, y_i <= 10⁸

Examples

• Input: points = [[1,1], [-1,1]]
• Output: True
• Why: Reflect over x = 0: (1,1) → (-1,1), (-1,1) → (1,1), matches set.
• Input: points = [[1,1], [-1,-1]]
• Output: False
• Why: No vertical line makes (1,1) and (-1,-1) symmetric (y differs).
• Input: points = [[0,0], [1,0], [2,0]]
• Output: True
• Why: Reflect over x = 1: (0,0) → (2,0), (1,0) → (1,0), (2,0) → (0,0).

Understanding the Problem: Finding the Mirror Line

To solve LeetCode 356: Line Reflection in Python, we need to determine if a vertical line exists that reflects all points into each other, preserving the set. A key insight: for such a line x = m, each point (x, y) must have a counterpart at (2m - x, y), and m must be consistent (the midpoint of x-coordinates). A naive approach—testing all possible lines—would be O(n²) or worse, impractical for 10⁴ points. Instead, we’ll use symmetry properties:

• Best Solution (Hash Set with Midpoint): O(n) time, O(n) space—checks reflections efficiently.
• Alternative Solution (Sorting with Symmetry): O(n log n) time, O(n) space—verifies via sorted order.

Let’s dive into the Best Solution—hash set with midpoint checking—and break it down step-by-step.

Best Solution: Hash Set with Midpoint Checking

Why This Is the Best Solution

The hash set with midpoint checking approach is the top choice because it’s highly efficient—O(n) time and O(n) space—using a set to track points and a consistent midpoint to verify symmetry. It finds the reflection line’s x-coordinate by averaging x-values of points and ensures all reflections exist in the set. It’s like placing a mirror and checking if every point has a twin on the other side—fast and clever!

How It Works

Here’s the strategy:

• Step 1: Build Point Set:
• Convert points to a set of tuples (handles duplicates).
• Step 2: Find Min and Max X:
• Compute min and max x-coordinates to find potential reflection line (midpoint).
• Step 3: Check Reflections:
• Midpoint m = (min_x + max_x) / 2.
• For each (x, y), check if (2m - x, y) exists in set.
• Step 4: Return:
• True if all reflections found, False otherwise.

Step-by-Step Example

Example: points = [[1,1], [-1,1]]

• Step 1: Build Set:
• point_set = {(1,1), (-1,1)}.
• Step 2: Find Min and Max X:
• Min x = -1, Max x = 1.
• Step 3: Check Reflections:
• Midpoint m = (-1 + 1) / 2 = 0.
• (1,1): Reflect = 2*0 - 1 = -1, check (-1,1) → in set.
• (-1,1): Reflect = 2*0 - (-1) = 1, check (1,1) → in set.
• Step 4: Result:
• All match, return True.

Example: points = [[1,1], [-1,-1]]

• Step 1: point_set = {(1,1), (-1,-1)}.
• Step 2: Min x = -1, Max x = 1.
• Step 3:
• m = 0.
• (1,1): Reflect = (2*0 - 1, 1) = (-1,1), not in set.
• Step 4: Return False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        # Step 1: Convert points to set of tuples
        point_set = set(map(tuple, points))

        # Step 2: Find min and max x
        min_x = float('inf')
        max_x = float('-inf')
        for x, y in point_set:
            min_x = min(min_x, x)
            max_x = max(max_x, x)

        # Step 3: Calculate reflection line midpoint
        mid = (min_x + max_x) / 2

        # Step 4: Check each point's reflection
        for x, y in point_set:
            reflect_x = 2 * mid - x
            if (reflect_x, y) not in point_set:
                return False

        return True

• Line 4: Convert to set for O(1) lookup.
• Line 7-10: Find min and max x-coordinates.
• Line 13: Compute midpoint of reflection line.
• Line 16-19: For each point, check reflection exists.
• Line 21: Return True if all match.
• Time Complexity: O(n)—single pass to build set and check.
• Space Complexity: O(n)—set stores unique points.

This is a symmetry-checking wizard!

Alternative Solution: Sorting with Symmetry Check

Why an Alternative Approach?

The sorting with symmetry check approach offers a different angle—O(n log n) time, O(n) space—sorting points by x and y, then verifying symmetry around a computed midpoint. It’s more explicit but slower due to sorting. It’s like lining up points and checking if they mirror perfectly—methodical and visual!

How It Works

• Step 1: Sort points by x, then y.
• Step 2: Find midpoint from first and last x.
• Step 3: Two-pointer check for symmetry.
• Step 4: Return result.

Step-by-Step Example

Example: points = [[1,1], [-1,1]]

• Step 1: Sort: [-1,1], [1,1].
• Step 2: Midpoint = (-1 + 1) / 2 = 0.
• Step 3:
• Left: [-1,1], Right: [1,1].
• Reflect -1 over 0 = 1, y matches (1=1).
• Step 4: True.

Example: points = [[1,1], [-1,-1]]

• Step 1: Sort: [-1,-1], [1,1].
• Step 2: Midpoint = 0.
• Step 3:
• [-1,-1] → reflect = [1,-1], [1,1] y differs (-1 ≠ 1).
• Step 4: False.

Code for Sorting Approach

Copy codeclass Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        # Step 1: Sort by x, then y
        points = sorted(set(map(tuple, points)))
        n = len(points)

        # Step 2: Handle single point or empty
        if n <= 1:
            return True

        # Step 3: Compute midpoint
        mid = (points[0][0] + points[-1][0]) / 2

        # Step 4: Two-pointer symmetry check
        left, right = 0, n - 1
        while left <= right:
            if (2 * mid - points[left][0]) != points[right][0] or points[left][1] != points[right][1]:
                return False
            left += 1
            right -= 1

        return True

• Line 4: Sort and deduplicate points.
• Line 7-9: Handle edge cases.
• Line 12: Midpoint from extremes.
• Line 15-19: Check symmetry with pointers.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(n)—sorted list.

It’s a sorted symmetry verifier!

Comparing the Two Solutions

• Hash Set (Best):
• Pros: O(n) time, O(n) space, fast and simple.
• Cons: Less explicit about line position.
• Sorting (Alternative):
• Pros: O(n log n) time, O(n) space, visual symmetry.
• Cons: Slower due to sorting.

Hash set wins for efficiency.

Additional Examples and Edge Cases

• [[0,0]]: True.
• [[1,1], [1,1]]: True (overlapping).
• [[0,0], [1,1]]: False.

Both handle these perfectly.

Complexity Breakdown

• Hash Set: Time O(n), Space O(n).
• Sorting: Time O(n log n), Space O(n).

Hash set’s speed shines.

Key Takeaways

• Hash Set: Check reflections fast!
• Sorting: Verify symmetry explicitly!
• Reflection: Midpoint is key.
• Python Tip: Sets optimize—see [Python Basics](/python/basics).

Final Thoughts: Mirror the Points

LeetCode 356: Line Reflection in Python is a geometric symmetry challenge. The hash set approach reflects with speed, while sorting offers a clear check. Want more geometry fun? Try LeetCode 149: Max Points on a Line or LeetCode 223: Rectangle Area. Ready to reflect? Head to Solve LeetCode 356 on LeetCode and mirror those points today!