# LeetCode 356: Line Reflection

## Problem Restatement

We are given a list of points on a 2D plane.

Each point is represented as:

```python
[x, y]
```

We need to decide whether there exists a vertical line such that reflecting every point across that line gives the same set of points.

A vertical line has this form:

```text
x = c
```

The line is parallel to the y-axis.

When a point `(x, y)` is reflected across `x = c`, the y-coordinate stays the same, and the x-coordinate changes to the opposite side.

The reflected point is:

```text
(2c - x, y)
```

The problem allows repeated points, but duplicates do not change whether the set is symmetric. The official statement asks whether a line parallel to the y-axis can reflect the given points symmetrically and notes that repeated points may appear.

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of points `points` |
| Point format | `[x, y]` |
| Output | `True` if a vertical reflection line exists, otherwise `False` |
| Reflection line | Must be parallel to the y-axis |
| Duplicate points | Allowed |

Example function shape:

```python
def isReflected(points: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```python
points = [[1, 1], [-1, 1]]
```

The points are symmetric around:

```text
x = 0
```

Reflecting `(1, 1)` across `x = 0` gives `(-1, 1)`.

Reflecting `(-1, 1)` across `x = 0` gives `(1, 1)`.

So the answer is:

```python
True
```

Example 2:

```python
points = [[1, 1], [-1, -1]]
```

The x-values are symmetric around `x = 0`, but the y-values do not match.

Reflecting `(1, 1)` across `x = 0` gives:

```python
[-1, 1]
```

But the input has:

```python
[-1, -1]
```

So the answer is:

```python
False
```

Example 3:

```python
points = [[1, 1], [1, 1], [1, 1]]
```

All points lie on the same vertical line.

The answer is:

```python
True
```

## First Thought: Try Many Lines

One possible idea is to try many candidate reflection lines.

For every pair of points, we could compute the midpoint of their x-coordinates and test that as a possible reflection line.

But this creates too many candidates.

If there are `n` points, there can be `O(n^2)` pairs.

The follow-up asks whether we can do better than `O(n^2)`, so we should avoid trying all possible lines.

## Key Insight

If a vertical reflection line exists, it has only one possible x-coordinate.

Look at the smallest x-coordinate and the largest x-coordinate among all points.

Call them:

```python
min_x
max_x
```

The leftmost point must reflect to the rightmost side.

So the reflection line must be exactly halfway between them:

```text
x = (min_x + max_x) / 2
```

Instead of storing the line as a floating-point number, store:

```python
center_sum = min_x + max_x
```

For a point `(x, y)`, its reflected x-coordinate must be:

```python
center_sum - x
```

So for every point:

```python
(x, y)
```

we need this point to exist:

```python
(center_sum - x, y)
```

That gives a linear-time check using a set.

## Algorithm

1. Create an empty set of points.
2. Scan all points.
3. Store every point as a tuple `(x, y)`.
4. Track the minimum x-coordinate.
5. Track the maximum x-coordinate.
6. Compute:

```python
center_sum = min_x + max_x
```

7. For every unique point `(x, y)` in the set:
   - Compute its mirror point:

```python
(center_sum - x, y)
```

   - Check whether the mirror point exists in the set.
   - If any mirror point is missing, return `False`.

8. Return `True`.

## Correctness

If a valid reflection line exists, the leftmost x-coordinate must reflect to the rightmost x-coordinate. Therefore, the line must be halfway between `min_x` and `max_x`.

So there is only one possible reflection line.

The algorithm tests exactly this line.

For any point `(x, y)`, reflecting across this line keeps `y` unchanged and changes `x` to:

```python
min_x + max_x - x
```

The algorithm checks that this reflected point exists in the original point set.

If every point has its reflected partner, then reflecting all points produces the same set, so the points are symmetric.

If any point lacks its reflected partner, then the candidate line fails. Since no other line can work, the answer must be `False`.

Therefore, the algorithm returns the correct result.

## Complexity

Let `n` be the number of input points.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One scan to build the set, one scan to verify mirrors |
| Space | `O(n)` | The set may store all unique points |

Duplicate points do not increase the logical set of points, and using a set handles them naturally.

## Implementation

```python
class Solution:
    def isReflected(self, points: list[list[int]]) -> bool:
        point_set = set()

        min_x = float("inf")
        max_x = float("-inf")

        for x, y in points:
            point_set.add((x, y))
            min_x = min(min_x, x)
            max_x = max(max_x, x)

        center_sum = min_x + max_x

        for x, y in point_set:
            mirror = (center_sum - x, y)

            if mirror not in point_set:
                return False

        return True
```

## Code Explanation

We store all points in a set:

```python
point_set = set()
```

Each point becomes a tuple because lists cannot be stored in a set:

```python
point_set.add((x, y))
```

At the same time, we track the leftmost and rightmost x-coordinates:

```python
min_x = min(min_x, x)
max_x = max(max_x, x)
```

The candidate reflection line is represented by:

```python
center_sum = min_x + max_x
```

This avoids floating-point precision issues.

For each point, we compute its mirror:

```python
mirror = (center_sum - x, y)
```

Then we check whether that mirror exists:

```python
if mirror not in point_set:
    return False
```

If every point passes the check, the set is symmetric:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isReflected([[1, 1], [-1, 1]]) is True

    assert s.isReflected([[1, 1], [-1, -1]]) is False

    assert s.isReflected([[1, 1], [1, 1], [1, 1]]) is True

    assert s.isReflected([[0, 0], [2, 0], [1, 1]]) is True

    assert s.isReflected([[0, 0], [2, 0], [1, 2]]) is True

    assert s.isReflected([[0, 0], [2, 0], [1, 2], [2, 2]]) is False

    assert s.isReflected([[-3, 1], [-1, 1], [-2, 2]]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[1,1],[-1,1]]` | Basic symmetric pair |
| `[[1,1],[-1,-1]]` | Same x symmetry but wrong y |
| Duplicate points | Confirms duplicates do not break the set logic |
| Point on center line | A point may reflect to itself |
| Multiple points on center line | All center-line points are valid |
| Missing mirror | Detects asymmetric set |
| Negative x-values | Confirms formula works with negatives |