Line Reflection

medium hash set math

Problem

Given n points in 2D, return whether there exists a vertical line that reflects all points onto themselves.

Inputpoints = [[1,1],[-1,1]]

Outputtrue

The y-axis (x = 0) is the reflection line — each point's mirror is the other.

points (x,y ;)

def is_reflected(points):
    xs = [p[0] for p in points]
    s = min(xs) + max(xs)
    seen = {(p[0], p[1]) for p in points}
    return all((s - x, y) in seen for x, y in seen)

function isReflected(points) {
  const xs = points.map(p => p[0]);
  const s = Math.min(...xs) + Math.max(...xs);
  const seen = new Set(points.map(p => p[0] + "," + p[1]));
  return points.every(([x, y]) => seen.has((s - x) + "," + y));
}

class Solution {
    public boolean isReflected(int[][] points) {
        int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
        Set seen = new HashSet<>();
        for (int[] p : points) {
            lo = Math.min(lo, p[0]); hi = Math.max(hi, p[0]);
            seen.add(p[0] + "," + p[1]);
        }
        int s = lo + hi;
        for (int[] p : points) if (!seen.contains((s - p[0]) + "," + p[1])) return false;
        return true;
    }
}

bool isReflected(vector>& points) {
    int lo = INT_MAX, hi = INT_MIN;
    set> seen;
    for (auto& p : points) { lo = min(lo, p[0]); hi = max(hi, p[0]); seen.insert({p[0], p[1]}); }
    int s = lo + hi;
    for (auto& p : points) if (!seen.count({s - p[0], p[1]})) return false;
    return true;
}

Explanation

If a single vertical mirror line reflects the whole set onto itself, that line has to sit exactly in the middle of the leftmost and rightmost points. So the only candidate is at x equal to (min(x) + max(x)) / 2 — there is no point testing any other line.

To avoid fractions, we work with the doubled value s = min(x) + max(x). A point (x, y) reflected across that line lands at (s - x, y): the y stays, and the x flips around the center.

We dump all points into a hash set for instant membership checks. Then for every point we verify its mirror (s - x, y) is also present. If even one mirror is missing, the reflection fails.

Example: points = [[1,1],[-1,1]]. Here s = 1 + (-1) = 0, so the mirror of (1,1) is (-1,1) and the mirror of (-1,1) is (1,1). Both exist, so the answer is true with the line at x = 0.

Because set lookups are constant time, checking all points is a single linear pass.

Time: O(n) Space: O(n)