LeetCode 356: Line Reflection

Problem Restatement

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

Each point is represented as:

[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:

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:

(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

Example function shape:

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

Examples

Example 1:

points = [[1, 1], [-1, 1]]

The points are symmetric around:

x = 0

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

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

So the answer is:

True

Example 2:

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:

[-1, 1]

But the input has:

[-1, -1]

So the answer is:

False

Example 3:

points = [[1, 1], [1, 1], [1, 1]]

All points lie on the same vertical line.

The answer is:

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:

min_x
max_x

The leftmost point must reflect to the rightmost side.

So the reflection line must be exactly halfway between them:

x = (min_x + max_x) / 2

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

center_sum = min_x + max_x

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

center_sum - x

So for every point:

(x, y)

we need this point to exist:

(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:

center_sum = min_x + max_x

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

(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:

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.

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

Implementation

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:

point_set = set()

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

point_set.add((x, y))

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

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

The candidate reflection line is represented by:

center_sum = min_x + max_x

This avoids floating-point precision issues.

For each point, we compute its mirror:

mirror = (center_sum - x, y)

Then we check whether that mirror exists:

if mirror not in point_set:
    return False

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

return True

Testing

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: