Как эффективно проверить наличие зеркальной пары точки с противоположным иксом

Что проверяют

Замените ли вы вложенный цикл O(n²) на хэш-множество и уточните ли условие до того, как писать код. Для data-ml следом часто просят то же самое на pandas или numpy для миллионов строк.

Как отвечать

Сначала уточните постановку, в ней три развилки: нужна хотя бы одна пара или зеркало у каждой точки; считается ли точка с x = 0 зеркалом самой себе; координаты целые или вещественные.

Базовое решение: сложить точки в set кортежей и для каждой (x, y) проверить, есть ли в нём (-x, y). Время O(n) в среднем, память O(n). Если точка на оси не должна считаться парой самой себе, добавьте условие x != 0 или храните счётчики через Counter, чтобы учесть дубли.

Альтернатива без хэш-таблицы: отсортировать по (y, abs(x)) и пройти по соседям, это O(n log n). Её стоит назвать, если интервьюер ограничит память.

Для вещественных координат точное сравнение не работает: 0.1 + 0.2 не равно 0.3. Координаты квантуют, например через round(x, 6), или переводят в целые, умножив на шаг сетки, и только потом кладут в множество.

В табличном варианте то же самое делается соединением:

m = df.merge(df.assign(x=-df.x), on=["x", "y"])

Непустой m означает, что пара есть. Для зеркала у каждой точки удобнее группировка по y и x.abs() с проверкой, что в группе встречаются оба знака. Такой код векторизован и на миллионах строк работает на порядки быстрее цикла через iterrows().

Где спотыкаются

Пишут двойной цикл и на нём останавливаются. Это O(n²), и на миллионе точек решение просто не дождётся ответа.

Не уточняют случай x = 0. Наивная проверка через set находит саму точку и возвращает True там, где настоящей пары нет, а merge соединяет такую строку саму с собой.

Сравнивают float напрямую и получают ложное «пары нет» из-за погрешности, которая набежала ещё при расчёте координат.