LeetCode 356 - Line Reflection
The problem gives us a collection of points on a 2D plane, where each point is represented as [x, y]. We need to determine whether there exists a vertical line, meaning a line parallel to the y-axis, such that reflecting every point across that line produces the exact same set…
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math
Solution
Problem Understanding
The problem gives us a collection of points on a 2D plane, where each point is represented as [x, y]. We need to determine whether there exists a vertical line, meaning a line parallel to the y-axis, such that reflecting every point across that line produces the exact same set of points.
A vertical reflection line always has the form:
$$x = c$$
for some constant c.
If a point (x, y) is reflected across this line, its reflected position becomes:
$$(2c - x,\ y)$$
The important requirement is that after reflecting all points, the resulting set must match the original set exactly. Every point must have a corresponding reflected counterpart. Points that lie directly on the reflection line are valid because they reflect onto themselves.
The input size can be as large as 10^4 points, and coordinates can range from -10^8 to 10^8. These constraints immediately tell us that an O(n^2) solution may become too slow in the worst case. We therefore need a more efficient approach, ideally linear or near-linear time.
Another subtle detail is that repeated points are allowed. This means the implementation must correctly handle duplicates without incorrectly rejecting valid reflections.
Several edge cases are important:
- Multiple points may lie exactly on the reflection line.
- Duplicate points may appear many times.
- Negative coordinates are allowed.
- The reflection line may not pass through any actual point.
- A naive midpoint computation using floating point arithmetic can introduce precision issues for large coordinates.
The key challenge is determining the correct reflection axis efficiently and verifying that every point has a valid mirrored counterpart.
Approaches
Brute Force Approach
The most direct approach is to try every possible vertical reflection line and check whether reflecting all points across that line preserves the set.
One way to derive candidate lines is to take every pair of points and compute the midpoint of their x-coordinates. Since reflected pairs must share the same midpoint, every valid reflection line must equal one of these midpoints.
For each candidate line:
- Reflect every point.
- Check whether the reflected point exists in the original set.
Using a hash set allows point lookup in constant time, but there can still be O(n) candidate lines, and each verification takes O(n), producing an O(n^2) solution overall.
This approach is correct because it explicitly tests every possible reflection axis, but it is too slow for the upper constraint of 10^4 points.
Optimal Approach
The key observation is that if a valid reflection line exists, then all reflected point pairs must share the same midpoint along the x-axis.
Suppose the smallest x-coordinate is minX and the largest x-coordinate is maxX. If the set is symmetric, then the reflection line must lie exactly halfway between them:
$$x = \frac{minX + maxX}{2}$$
This means we do not need to guess the reflection line. It is uniquely determined by the extreme x-values.
Instead of storing the midpoint as a floating point number, we store:
$$sum = minX + maxX$$
Then for every point (x, y), its reflected counterpart must be:
$$(sum - x,\ y)$$
Using a hash set for all points allows constant-time existence checks.
This reduces the problem to a single pass verification after computing minX and maxX.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Tries multiple candidate reflection lines |
| Optimal | O(n) | O(n) | Uses the invariant that all reflected pairs share the same midpoint |
Algorithm Walkthrough
- Iterate through all points to determine the minimum and maximum x-coordinates.
These two values define the only possible reflection axis. If the set is symmetric, the line must be exactly halfway between the leftmost and rightmost points. 2. Compute the reflection sum:
$$sum = minX + maxX$$
Instead of storing the reflection line as a floating point value, we use this integer sum to avoid precision issues.
- Insert every point into a hash set.
The hash set allows constant-time lookup when checking whether reflected counterparts exist.
2. Iterate through each point (x, y).
For symmetry to hold, the reflected point:
$$(sum - x,\ y)$$
must also exist in the set.
- If any reflected counterpart is missing, immediately return
False.
A single missing reflection proves that no valid vertical reflection line exists.
2. If all points pass the check, return True.
Why it works
The algorithm works because any valid vertical reflection line must lie exactly halfway between the minimum and maximum x-coordinates. Once this axis is fixed, every point must have a mirrored counterpart at the corresponding reflected position. The hash set verification ensures this condition holds for the entire set. Since every point is checked against the uniquely determined reflection axis, the algorithm correctly determines whether the point set is symmetric.
Python Solution
from typing import List
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:
min_x = min(min_x, x)
max_x = max(max_x, x)
point_set.add((x, y))
reflection_sum = min_x + max_x
for x, y in points:
reflected_point = (reflection_sum - x, y)
if reflected_point not in point_set:
return False
return True
The implementation begins by scanning all points once to compute the smallest and largest x-coordinates. At the same time, every point is inserted into a hash set for fast lookup.
The variable reflection_sum stores min_x + max_x, which avoids floating point arithmetic entirely. This is important because coordinates can be very large, and integer arithmetic guarantees exact comparisons.
The second loop verifies symmetry. For every point (x, y), the algorithm computes its reflected counterpart (reflection_sum - x, y) and checks whether it exists in the set.
If any reflected point is missing, the function immediately returns False. Otherwise, after all checks pass, the set is symmetric and the function returns True.
Go Solution
func isReflected(points [][]int) bool {
pointSet := make(map[[2]int]bool)
minX := int(^uint(0) >> 1)
maxX := -minX - 1
for _, point := range points {
x, y := point[0], point[1]
if x < minX {
minX = x
}
if x > maxX {
maxX = x
}
pointSet[[2]int{x, y}] = true
}
reflectionSum := minX + maxX
for _, point := range points {
x, y := point[0], point[1]
reflected := [2]int{reflectionSum - x, y}
if !pointSet[reflected] {
return false
}
}
return true
}
The Go implementation follows the same logic as the Python version, but there are a few language-specific details.
Go does not have a built-in tuple type, so a fixed-size array [2]int is used as the hash map key. Arrays are comparable in Go, which makes them valid map keys.
The implementation initializes minX and maxX manually because Go does not provide built-in infinity values for integers. The expression:
int(^uint(0) >> 1)
computes the maximum possible integer value for the platform.
All arithmetic uses integers, which avoids precision problems and safely handles the coordinate range specified in the constraints.
Worked Examples
Example 1
Input:
points = [[1,1],[-1,1]]
Step 1: Compute min and max x-values
| Point | minX | maxX |
|---|---|---|
| (1,1) | 1 | 1 |
| (-1,1) | -1 | 1 |
Now:
$$reflectionSum = minX + maxX = -1 + 1 = 0$$
This corresponds to reflection line:
$$x = 0 / 2 = 0$$
Step 2: Build hash set
{
(1,1),
(-1,1)
}
Step 3: Verify reflections
| Original Point | Reflected Point | Exists? |
|---|---|---|
| (1,1) | (-1,1) | Yes |
| (-1,1) | (1,1) | Yes |
All reflected points exist, so the answer is True.
Example 2
Input:
points = [[1,1],[-1,-1]]
Step 1: Compute min and max x-values
| Point | minX | maxX |
|---|---|---|
| (1,1) | 1 | 1 |
| (-1,-1) | -1 | 1 |
Now:
$$reflectionSum = 0$$
Reflection line:
$$x = 0$$
Step 2: Build hash set
{
(1,1),
(-1,-1)
}
Step 3: Verify reflections
| Original Point | Reflected Point | Exists? |
|---|---|---|
| (1,1) | (-1,1) | No |
The reflected counterpart is missing, so the answer is False.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One pass to build the set and one pass to verify reflections |
| Space | O(n) | Hash set stores all unique points |
The algorithm performs two linear scans over the input. Each hash set lookup is expected O(1) time, so the total runtime remains linear. The extra memory usage comes from storing all points in the hash set.
Test Cases
sol = Solution()
# Provided examples
assert sol.isReflected([[1, 1], [-1, 1]]) == True # symmetric about x = 0
assert sol.isReflected([[1, 1], [-1, -1]]) == False # y values do not match
# Single point
assert sol.isReflected([[5, 7]]) == True # single point always symmetric
# Points directly on reflection line
assert sol.isReflected([[0, 0], [1, 0], [-1, 0]]) == True # center point reflects to itself
# Duplicate points
assert sol.isReflected([[1, 1], [-1, 1], [1, 1]]) == True # duplicates should not break logic
# Even reflection line
assert sol.isReflected([[2, 3], [4, 3]]) == True # reflection line x = 3
# Missing reflected pair
assert sol.isReflected([[2, 3], [4, 3], [5, 3]]) == False # point at x = 5 has no mirror
# Negative coordinates
assert sol.isReflected([[-3, 2], [-1, 2]]) == True # reflection line x = -2
# Multiple symmetric layers
assert sol.isReflected([
[-2, 1],
[2, 1],
[-1, 2],
[1, 2]
]) == True # symmetric about x = 0
# Different y coordinates prevent reflection
assert sol.isReflected([
[-2, 1],
[2, 2]
]) == False # reflected y-coordinate mismatch
# Large coordinates
assert sol.isReflected([
[-100000000, 5],
[100000000, 5]
]) == True # tests large integer handling
Test Summary
| Test | Why |
|---|---|
[[1,1],[-1,1]] |
Basic valid symmetry |
[[1,1],[-1,-1]] |
Different y-values break symmetry |
[[5,7]] |
Single-point edge case |
[[0,0],[1,0],[-1,0]] |
Point on reflection axis |
| Duplicate points | Ensures duplicates do not affect correctness |
[[2,3],[4,3]] |
Reflection line not at x = 0 |
| Missing mirrored point | Detects incomplete symmetry |
| Negative coordinates | Validates handling of negatives |
| Multiple symmetric pairs | Tests more complex symmetry |
| Different y-values | Reflection requires identical y |
| Large coordinates | Ensures integer arithmetic remains safe |
Edge Cases
Points lying directly on the reflection line
A point exactly on the reflection line reflects onto itself. This can easily cause bugs if the implementation assumes every point must pair with a distinct second point.
For example:
[[0,0], [1,0], [-1,0]]
The point (0,0) reflects to itself when the line is x = 0.
The implementation handles this naturally because the reflected coordinate calculation produces the same point, and the hash set lookup succeeds.
Duplicate points
The problem explicitly allows repeated points. A naive implementation that relies on counts or pair removals can accidentally reject valid inputs or double-process points.
For example:
[[1,1], [-1,1], [1,1]]
The solution avoids this issue by storing points in a hash set and only checking existence of reflected counterparts. Duplicate entries do not affect correctness.
Large coordinate values
Coordinates can be as large as 10^8, which means floating point midpoint calculations could introduce precision concerns in some languages or implementations.
Instead of computing:
$$mid = (minX + maxX) / 2$$
the algorithm stores:
$$reflectionSum = minX + maxX$$
and checks reflections using integer arithmetic only. This guarantees exact comparisons and avoids precision-related bugs entirely.