Line Reflection

Line Reflection

What is this problem about?

The "Line Reflection interview question" asks you to determine if there exists a vertical line that reflects a given set of points on a 2D plane. For every point (x, y) in the set, there must be a corresponding point (x', y) such that the distance from x to the vertical line is the same as the distance from x' to the line. This "Line Reflection coding problem" combines geometry with efficient data lookup.

Why is this asked in interviews?

This problem is asked by companies like Google and Yandex to test a candidate's ability to apply "Hash Table interview pattern" to geometric problems. It evaluates whether you can derive the mathematical properties of a reflection line and then use a set or map to verify those properties across all points in O(n) time.

Algorithmic pattern used

The first step is to find the potential reflection line. The line must be exactly in the middle of the leftmost and rightmost points. Let minX be the minimum x-coordinate and maxX be the maximum x-coordinate. The reflection line is x = (minX + maxX) / 2. Then, for every point (x, y), there must exist a point (minX + maxX - x, y) in the set. Using a Hash Set to store all points as strings or pairs allows for O(1) verification.

Example explanation

Points: [[1, 1], [-1, 1]]

1. minX = -1, maxX = 1.
2. Potential line: x = (-1 + 1) / 2 = 0.
3. Check point [1, 1]: Its reflection across x=0 is (-1, 1). It exists.
4. Check point [-1, 1]: Its reflection across x=0 is (1, 1). It exists. Result: True.

Common mistakes candidates make

• Floating point issues: Using division for the line coordinate. It's safer to use the sum minX + maxX as a constant and check if x1 + x2 == constant.
• Duplicate points: Not realizing that the same point can appear multiple times, or not handling it correctly in a Set.
• O(n^2) search: Forgetting to use a Hash Set and instead searching for each reflection point manually.

Interview preparation tip

Geometric problems often have a "global" property that can be derived from the extrema (min/max). Once you find the potential symmetry point or line, the problem usually reduces to a membership check in a set.