Problem Description

You are given n points on a 2D plane. Your task is to determine if there exists a vertical line (parallel to the y-axis) such that when all points are reflected across this line, the resulting set of points is identical to the original set.

A reflection across a vertical line means that for a point (x, y) and a vertical line at position x = c, the reflected point would be at (2c - x, y). The y-coordinate remains unchanged while the x-coordinate is mirrored across the line.

The problem asks you to return true if such a line of reflection exists, and false otherwise.

Key points to consider:

• The line of reflection must be vertical (parallel to the y-axis)
• After reflection, the set of points must be exactly the same as the original set
• Points can be repeated in the input (duplicates are allowed)
• The reflection line doesn't need to pass through any of the given points

For example:

• Points [(1,1), (3,1)] can be reflected across the line x = 2 to get the same set
• Points [(1,1), (2,2)] cannot be reflected across any vertical line to get the same set

The solution works by finding the minimum and maximum x-coordinates among all points. If a line of reflection exists, it must be at x = (min_x + max_x) / 2. Then it checks if every point (x, y) has its corresponding reflected point (min_x + max_x - x, y) in the original set.

Intuition

To find if points can be reflected across a vertical line to produce the same set, we need to first identify where this line of reflection could possibly be located.

Think about what happens when we reflect points across a vertical line - the leftmost point becomes the rightmost point and vice versa. This means the line of reflection must be exactly in the middle of the leftmost and rightmost points. If we have a minimum x-coordinate of min_x and maximum x-coordinate of max_x, the line of reflection must be at x = (min_x + max_x) / 2.

Why is this the only possible location? Consider any other position for the line:

• If the line is to the left of center, the reflected rightmost point would extend beyond the original rightmost point
• If the line is to the right of center, the reflected leftmost point would extend beyond the original leftmost point
• Either case would create new points not in the original set

Once we know where the line must be, we need to verify that every point has its reflection in the original set. For a point (x, y) and reflection line at x = c, the reflected point is at (2c - x, y). Since c = (min_x + max_x) / 2, we get 2c = min_x + max_x, so the reflected point is at (min_x + max_x - x, y).

The verification process is straightforward: for each point in our set, check if its reflected counterpart exists. If even one point lacks its reflection, no valid line exists. We use a set data structure for O(1) lookup time when checking if reflected points exist.

This approach elegantly reduces the problem from finding a line to simply verifying if a specific line (the only candidate) works.

Solution Approach

The implementation follows a straightforward approach with three main steps:

1. Find the bounds and create a point set: We iterate through all points once to:

   • Track the minimum x-coordinate (min_x) and maximum x-coordinate (max_x)
   • Store all unique points in a set for O(1) lookup later

   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))

2. Calculate the reflection line position: The sum s = min_x + max_x represents twice the x-coordinate of the reflection line. We don't need to divide by 2 because we'll use this sum directly in our reflection formula.

   s = min_x + max_x

3. Verify all points have their reflections: For each point (x, y), we check if its reflection (s - x, y) exists in the point set. The reflection formula comes from:

   • Reflection line is at x = s/2
   • Distance from point to line: |x - s/2|
   • Reflected x-coordinate: s/2 - (x - s/2) = s - x

   return all((s - x, y) in point_set for x, y in points)

The all() function returns True only if every point has its corresponding reflection in the set. If any point lacks its reflection, it immediately returns False.

Time Complexity: O(n) where n is the number of points - we iterate through the points twice (once to build the set and find bounds, once to verify reflections).

Space Complexity: O(n) for storing the point set.

The elegance of this solution lies in avoiding floating-point arithmetic by working with the sum s = min_x + max_x directly instead of calculating the actual line position at s/2.

Example Walkthrough

Let's walk through the solution with the points: [(0,0), (1,0), (3,0), (4,0)]

Step 1: Find bounds and create point set

• Iterate through all points:
  • Point (0,0): min_x = 0, max_x = 0
  • Point (1,0): min_x = 0, max_x = 1
  • Point (3,0): min_x = 0, max_x = 3
  • Point (4,0): min_x = 0, max_x = 4
• Final bounds: min_x = 0, max_x = 4
• Point set: {(0,0), (1,0), (3,0), (4,0)}

Step 2: Calculate reflection line position

• s = min_x + max_x = 0 + 4 = 4
• This means the reflection line is at x = 4/2 = 2

Step 3: Verify all points have reflections

• Check (0,0): reflection at (4-0, 0) = (4,0) ✓ exists in set
• Check (1,0): reflection at (4-1, 0) = (3,0) ✓ exists in set
• Check (3,0): reflection at (4-3, 0) = (1,0) ✓ exists in set
• Check (4,0): reflection at (4-4, 0) = (0,0) ✓ exists in set

All points have their reflections in the original set, so return true.

Visual representation:

Original points:    0   1   2   3   4  (x-axis)
                    •   •   |   •   •
                            ^
                     reflection line at x=2

When we reflect across x=2:

• (0,0) ↔ (4,0)
• (1,0) ↔ (3,0)

The reflected set {(4,0), (3,0), (1,0), (0,0)} is identical to the original set, confirming our answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of points in the input list.

• The first loop iterates through all n points to find min_x and max_x, and to build the point_set. Each operation inside the loop (min comparison, max comparison, and set insertion) takes O(1) time on average. This results in O(n) time.
• The all() function with the generator expression iterates through all n points once, and for each point, it performs a set lookup operation (s - x, y) in point_set, which takes O(1) time on average. This also results in O(n) time.
• Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(n), where n is the number of points in the input list.

• The point_set stores all unique points from the input list. In the worst case, all points are unique, so the set will contain n elements, requiring O(n) space.
• Other variables (min_x, max_x, s) use constant space O(1).
• Overall space complexity: O(n)

Common Pitfalls

1. Handling Duplicate Points Incorrectly

A common mistake is not properly handling duplicate points in the input. Some might try to use a list instead of a set, leading to incorrect results when checking for reflections.

Problem Example:

points = [[1,1], [1,1], [3,1]]  # Point (1,1) appears twice

Using a list would fail because you'd check for the reflection of (1,1) twice, but the reflected point (3,1) only appears once.

Solution: Always use a set to store unique points, which automatically handles duplicates and provides O(1) lookup time.

2. Integer Overflow or Precision Issues

When calculating min_x + max_x, the sum might overflow in languages with fixed integer sizes, or cause precision issues if using floating-point division.

Problem Example:

# If min_x = -10^9 and max_x = 10^9
# Some might incorrectly calculate the line position as:
line_x = (min_x + max_x) / 2  # Potential precision loss
reflected_x = 2 * line_x - x   # Compounds the precision error

Solution: Work with the sum directly (s = min_x + max_x) and use the formula (s - x, y) for reflection, avoiding division entirely. This maintains exact integer arithmetic.

3. Forgetting Edge Cases

Missing important edge cases can lead to incorrect results:

Empty Input:

points = []  # Should return True (empty set is symmetric)

Single Point:

points = [[0,0]]  # Should return True (single point is symmetric)

Solution: Add edge case handling:

if not points:
    return True  # Empty set is symmetric

4. Incorrect Reflection Formula

A common mathematical error is using the wrong reflection formula, especially when trying to work with the actual line position.

Incorrect approach:

# Wrong: Trying to reflect using distance calculation
line_x = (min_x + max_x) / 2
reflected_x = x + 2 * (line_x - x)  # This is incorrect!

Correct approach:

# Correct: Using the sum directly
s = min_x + max_x
reflected_x = s - x  # Simple and correct

5. Not Considering Points ON the Reflection Line

Points that lie exactly on the reflection line reflect to themselves. Some implementations might incorrectly handle this case.

Problem Example:

points = [[2,1], [2,2], [2,3]]  # All points on x=2
# The reflection line is at x=2, and all points reflect to themselves

Solution: The formula (s - x, y) naturally handles this case correctly. When x = s/2, then s - x = s/2, so the point maps to itself, which should exist in the set.