356. Line Reflection | Detailed Explanation

Description

Given n points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically.

In other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points’ set is the same as the reflected ones.

Note that there can be repeated points.

Example 1

Input: [[1, 1], [-1, 1]]
Output: true
Explanation: We can choose the line x = 0

Example 2

Input: [[1, 1], [-1, -1]]
Output: false
Explanation: We can't choose a line

Solution

Any line parallel to the Y-axis is characterized by the value of x. We can reflect the point (x, y) with respect to a line parallel to the Y-axis by choosing a value for x: then the point (x, y) will become (x1, y). In other words, when reflecting, the y-coordinate remains the same, and the x-coordinate changes to x1.

Let’s assume such a line exists, then the leftmost point must be reflected into the rightmost point. If the leftmost point is not reflected into the rightmost point, then there is no point in the set to which it could be reflected.

From this, we can deduce two facts:

• The leftmost point min_x must be reflected into the rightmost point max_x
• The only candidate for a suitable vertical line will be the line X = (min_x + max_x) / 2

Let’s consider the following example:

The reflection line is X = (min_x + max_x) / 2 = (-1 + 2) / 2 = 0.5. Let’s check if all points are correctly reflected with respect to this line. Let’s assume we have an initial set of points stored in the set s = {(-1, 1), (0, 0), (1, 0), (2, 1)}. We can perform the check as follows:

If the point reflected from (x, y) is not present in the set s, then the line X = k does not satisfy the problem’s condition

But how do we find the coordinates of the reflected point? To do this, we need to check if the point ((k + k) — x, y), where k is the coordinate of the reflection line, is present in the set s. If it is, then the point (x, y) reflects to ((k + k) — x, y) with the line X = k.

Let’s step-by-step solve the example above:

1. (-1, 1): ((0.5 + 0.5) — (-1), 1) = (2, 1) is present in the set s, so the point (-1, 1) reflects to (2, 1) with the reflection line X = 0.5
2. (0, 0): ((0.5 + 0.5) — 0, 0) = (1, 0) is present in the set s, so the point (0, 0) reflects to (1, 0) with the reflection line X = 0.5
3. (1, 0): ((0.5 + 0.5) — 1, 0) = (0, 0) is present in the set s, so the point (1, 0) reflects to (0, 0) with the reflection line X = 0.5
4. (2, 1): ((0.5 + 0.5) — 2, 1) = (-1, 1) is present in the set s, so the point (2, 1) reflects to (-1, 1) with the reflection line X = 0.5

All points are correctly reflected, so the reflection line exists.

Note that the calculation of the x-coordinate for the reflected point is always the same. Moreover, we always double the value of the line’s coordinate by 2. Therefore, there is no need to divide the expression min_x + max_x by 2 since we always multiply the line’s value by 2 afterwards.

The Python solution would look like this:

This solution is efficient as it works in O(n) time and O(n) space, where n is the length of the points array.