356. Line Reflection

1. Условие задачи

Дано: n точек на плоскости, каждая задана парой [x, y]. Точки могут повторяться.

Нужно: понять, существует ли вертикальная прямая (параллельная оси y), относительно которой весь набор точек симметричен. То есть если отразить каждую точку относительно этой прямой, получится тот же самый набор точек.

Ограничения: 1 <= n <= 10^4, координаты целые, от -10^8 до 10^8. В follow-up просят решение быстрее O(N²).

Пример 1: points = [[1, 1], [-1, 1]] → true. Прямая x = 0: точка (1, 1) отражается в (-1, 1) и наоборот.

Пример 2: points = [[1, 1], [-1, -1]] → false. Подходящей прямой нет: отражение по вертикали не меняет y, а у точек y разные.

Что на самом деле значит «тот же набор»

Условие на LeetCode сформулировано мутно, и в обсуждениях к нему много вопросов. Уточним по тому, как работают тесты:

• Количество копий не важно. [[1, 1], [1, 1], [-1, 1]] → true. Две копии точки (1, 1) обе отражаются в одну (-1, 1) — и этого достаточно. (Версию, где копии важны, разберём в конце — её дают в Яндексе.)
• Точка на самой прямой отражается сама в себя. Для [[0, 5], [-1, 1], [1, 1]] ответ true — точка (0, 5) лежит на прямой x = 0 и пары ей не нужно.
• Прямая может проходить по дробной координате. Для [[0, 0], [1, 0]] ответ true, прямая x = 0.5.

2. Решение

Как отразить точку относительно прямой x = c

Без этой формулы дальше никуда, поэтому выведем её сразу.

Возьмём точку (x, y) и вертикальную прямую x = c. Отражение по вертикальной прямой двигает точку только по горизонтали, поэтому y не меняется. Остаётся найти новый икс x'.

Прямая проходит ровно посередине между точкой и её отражением, то есть c — среднее арифметическое x и x':

[ \frac{x + x’}{2} = c \quad\Rightarrow\quad x’ = 2c - x ]

Итого: отражение точки (x, y) относительно прямой x = c — это (2c - x, y).

Проверим на примере 1: прямая c = 0, точка (1, 1) → (2 · 0 - 1, 1) = (-1, 1). Всё сходится.

Ось может быть только одна

Где может стоять ось? Посмотрим на две крайние точки: самую левую с иксом minX и самую правую с иксом maxX. Все точки набора лежат между ними, и после отражения должны остаться там же — других точек у нас нет.

Отражение работает как зеркало: чем левее точка, тем правее её отражение. Значит, самая левая точка улетает дальше всех вправо, и попасть она должна ровно в maxX: правее точек нет, а если она окажется левее maxX, то самая правая точка, наоборот, улетит левее minX — где точек тоже нет.

Получается, что крайние точки обязаны быть парой, а ось стоит ровно посередине между ними:

[ c = \frac{minX + maxX}{2} ]

Итак, ось, если она существует, ровно одна. Ровно это и говорят подсказки к задаче на LeetCode.

Искать ось не нужно — её можно сразу посчитать. Остаётся проверить, что у каждой точки есть пара (2c - x, y).

Решение: хеш-сет (O(N))

Чтобы проверка «есть ли точка» стоила O(1) в среднем, складываем точки в множество кортежей. Это подход подавляющего большинства топовых решений. Заодно множество автоматически решает вопрос с дубликатами: копии схлопываются, а сравнение идёт как раз по множеству точек.

Важно именно множество, а не список. Если написать [2 * c - x, y] not in points, каждая проверка станет линейным проходом по списку, и время вырастет до O(N²). В Solutions есть решение с заголовком «Time complexity O(n), Space complexity O(1)», устроенное именно так — хороший повод на собеседовании проговорить стоимость каждой операции вслух.

Алгоритм по шагам

1. Сложить все точки в множество seen кортежей (x, y).
2. Найти minX и maxX.
3. Посчитать ось c = (minX + maxX) / 2.
4. Для каждой точки (x, y) из множества проверить, что (2c - x, y) тоже лежит в seen.
5. Если хоть одной пары не нашлось — false. Если проверка прошла для всех — true.

Визуализация на points = [[1, 1], [3, 1], [2, 5], [1, 4], [3, 4], [3, 4]]

minX = 1, maxX = 3, значит c = (1 + 3) / 2 = 2. Множество: {(1, 1), (3, 1), (2, 5), (1, 4), (3, 4)} — дубликат (3, 4) схлопнулся.

y
5 |      *          (2, 5) лежит на оси
4 |  *   |   *      (1, 4) <-> (3, 4)
3 |      |
2 |      |
1 |  *   |   *      (1, 1) <-> (3, 1)
  +--1---2---3--- x
         ось x = 2

Все отражения нашлись → true.

А теперь испортим пример: заменим (1, 1) на (1, 2). Крайние иксы не поменялись, c = 2, но для точки (1, 2) ищем (3, 2) — такой нет → false. Никакая другая ось не спасёт: она обязана быть посередине между крайними.

Код на Python

class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        # 1. Складываем точки в множество — дубликаты схлопнутся,
        #    а проверка «есть ли точка» станет O(1)
        seen = {(x, y) for x, y in points}
        # 2. Ось может быть только посередине между крайними точками
        c = (min(x for x, _ in seen) + max(x for x, _ in seen)) / 2
        # 3. У каждой точки должна найтись пара (2c - x, y)
        for x, y in seen:
            if (2 * c - x, y) not in seen:
                return False
        return True

Идём мы именно по seen, а не по points: результат тот же, но повторные копии не проверяем зря.

Почему float здесь не мешает

Ось c может быть дробной: у [[0, 0], [1, 0]] это 0.5. Перевести c в int нельзя, но и не нужно:

• 2 * c — всегда целое число, просто хранится как float (например, 4.0), причём без погрешности: координаты до 10^8, а точности float хватает с огромным запасом.
• Значит, и 2 * c - x — целое, только в виде float: 3.0.
• В Python 3.0 == 3 и hash(3.0) == hash(3), поэтому кортеж (3.0, 1) находится в множестве, где лежит (3, 1).

Вариант без дробей: удвоенная ось S

Если float всё-таки не хочется (или пишешь на языке, где 3.0 и 3 — разные ключи: например, в Java-решениях с ключом-строкой "3.0a1" и "3a1" не совпадут), заметим, что в формулах c встречается только в виде 2c. Так давайте сразу хранить удвоенную координату оси:

[ S = 2c = minX + maxX, \qquad x’ = 2c - x = S - x ]

Всё в целых числах, и заодно получаем красивую формулировку: точки (x₁, y) и (x₂, y) симметричны, если x₁ + x₂ = S — у всех симметричных пар одинаковая сумма иксов, равная сумме крайних. По смыслу S - x = minX + (maxX - x) тоже наглядно (так объясняет Stefan Pochmann в одном из самых популярных решений): maxX - x — насколько точка отстоит от правого края, и ровно на столько же отступаем от левого.

class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        seen = {(x, y) for x, y in points}
        # Удвоенная координата оси — целое число, дробей нет
        S = min(x for x, _ in seen) + max(x for x, _ in seen)
        for x, y in seen:
            if (S - x, y) not in seen:
                return False
        return True

Дальше в разборе пользуемся S.

Альтернатива без хеширования: сортировка (O(N log N))

Если хеш-таблицы по какой-то причине под запретом, есть красивое решение от Stefan Pochmann: отразим все точки разом и сравним два набора. Чтобы сравнение не зависело от порядка, отсортируем оба:

class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        # 1. Убираем дубликаты и сортируем: крайние x — первая и последняя точки
        pts = sorted(set(map(tuple, points)))
        S = pts[0][0] + pts[-1][0]
        # 2. Отражаем все точки и сортируем — набор должен совпасть с исходным
        return pts == sorted((S - x, y) for x, y in pts)

После сортировки кортежи упорядочены по x, поэтому pts[0][0] — это minX, а pts[-1][0] — maxX. Работает за O(N log N) из-за сортировок. Это тоже лучше O(N²), так что follow-up формально закрыт, но хеш-сет всё равно быстрее.

set(...) здесь обязателен. Без него версия ломается на [[1, 1], [1, 1], [-1, 1]]: сортированный исходник [(-1, 1), (1, 1), (1, 1)], а отражённый [(-1, 1), (-1, 1), (1, 1)] — списки разные, хотя правильный ответ true.

Краевые случаи

• Одна точка — minX = maxX = x, c = x, точка отражается сама в себя → true.
• Все точки на одной вертикали — то же самое: ось проходит через них, каждая точка — своя пара → true.
• Дубликаты — схлопываются множеством и на ответ не влияют.
• Дробная ось — [[0, 0], [1, 0]]: c = 0.5, отражение (0, 0) — это (2 · 0.5 - 0, 0) = (1.0, 0), и оно находится в множестве. С S = 1 то же самое в целых: (1 - 0, 0) = (1, 0).
• Разные y у точек с «правильными» x — [[1, 1], [-1, -1]]: c = 0, ищем (-1, 1) — нет → false. Отражение не меняет y, поэтому по одним иксам симметрию не проверить.
• Отрицательные координаты — формула 2c - x работает без изменений.

3. Сложность алгоритма

• Построение множества — один проход по N точкам, O(N).
• Поиск minX и maxX — ещё два линейных прохода, O(N).
• Проверка — по одной операции in для каждой из не более чем N точек, каждая O(1) в среднем — итого O(N).

Итог по времени: O(N) в среднем (у сортировочной версии — O(N log N)).

Итог по памяти: O(N) на множество точек.

Вариация от Яндекса: с учётом кратности точек

На собеседованиях в Яндексе дают такую версию:

Дан набор точек на плоскости, точки могут повторяться. Нужно проверить, существует ли вертикальная прямая, после отражения относительно которой получается ровно тот же набор с учётом копий: если слева две одинаковые точки, то и справа должно быть ровно две их копии.

Чем отличается от оригинала: теперь важно не только какие точки есть, но и сколько копий у каждой. [[1, 1], [1, 1], [-1, 1]] в оригинале — true, а здесь — false: слева одна копия, справа две.

Что остаётся прежним: ось. Рассуждение про крайние точки нигде не использовало количество копий — minX и maxX от дубликатов не зависят. Поэтому по-прежнему S = minX + maxX.

Что меняется: проверка. Теперь мало, чтобы отражение просто нашлось, — у точки и её отражения должно быть одинаковое количество копий. Для этого вместо set берём Counter:

from collections import Counter

class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        # 1. Считаем, сколько раз встречается каждая точка
        cnt = Counter(map(tuple, points))
        # 2. Ось та же: посередине между крайними x
        S = min(x for x, _ in cnt) + max(x for x, _ in cnt)
        # 3. У каждой точки отражение должно встречаться столько же раз
        for (x, y), k in cnt.items():
            if cnt[(S - x, y)] != k:
                return False
        return True

Если отражения нет вовсе, cnt[(S - x, y)] вернёт 0, и сравнение с k >= 1 провалится — отдельный in не нужен.

А если на оси несколько точек? Отдельно обрабатывать их не нужно. Точка (x, y) лежит на оси, если x = S - x, то есть её отражение — она сама. В проверке cnt[(S - x, y)] != k слева и справа оказывается одно и то же число, и return False для такой точки не сработает никогда. Поэтому на оси может быть сколько угодно копий одной точки (в том числе нечётное число) и сколько угодно разных точек:

Сложность та же: O(N) по времени, O(N) по памяти.

Забавный момент: сортировка без set, которая ломалась в оригинале, здесь становится правильным решением — сравнение двух отсортированных списков как раз проверяет совпадение с учётом копий. Это и есть самая первая версия решения Stefan Pochmann, написанная до того, как в задаче разрешили повторы: points.sort(); return points == sorted([S - x, y] for x, y in points).

Справочно: проверка одной строкой

Во всех решениях выше проверка написана обычным циклом: нашли точку без пары — return False, дошли до конца — return True. Если хочется короче, этот цикл сворачивается в одну строку через all(...) с генератором — логика та же, all тоже останавливается на первом False.

Для оригинальной задачи (множество точек):

return all((2 * c - x, y) in seen for x, y in seen)

Для вариации Яндекса (с учётом копий):

return all(cnt[(S - x, y)] == k for (x, y), k in cnt.items())

Вывод

Паттерн задачи: сначала рассуждением найти единственный возможный ответ, а потом проверить его хешированием. Здесь это наблюдение «у всех симметричных пар одинаковая сумма x, равная minX + maxX», а проверка — та же схема, что в Two Sum: для каждого элемента ищем в хеш-таблице его «дополнение» S - x. Бонусом — два урока: понимать, почему дробная ось не ломает проверку (а если хочется целых чисел — перейти к удвоенной оси S), и внимательно читать, что значит «тот же набор» — просто набор точек или набор с учётом копий. От этого зависит, set нам нужен или Counter.

🐆