Задача с собеседования в Google. 939. Minimum Area Rectangle

Задача.

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

Если такого прямоугольника нет – в качестве результата вернуть 0.

Например,
Для точек: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Ответ 2.

Ссылка на leetcode: https://leetcode.com/problems/minimum-area-rectangle/

Решение.

Первое решение, которое приходит в голову – это полный перебор. Нам нужно перебрать все наборы из 4 разных точек, проверить, что они образуют прямоугольник с осями, параллельными осям x и y, вычислить площадь и найти минимальную среди них.
Такой перебор можно организовать при помощи 4 вложенных друг в друга циклов, каждый из которых это цикл по всем заданным точкам.
Для произвольных 4 точек: A, B, C, D, условия, что они образуют прямоугольник, параллельный осям x и y:

xA == xB
yA != yB
xB != xC
yB == yC
xC == xD
yD == yA

Если эти 4 точки образуют прямоугольник, параллельный осям x и y, так, как изображено на рисунке, то площадь будет равна:

S = |yB - yA| * |xD - xA|

В коде это выглядит следующим образом:

public int minAreaRect(int[][] points) { int minArea = Integer.MAX_VALUE; for (int pointA[] : points) { for (int pointB[]: points) { for (int pointC[] : points) { for (int pointD[] : points) { if (pointA[0] == pointB[0] && pointA[1] != pointB[1] && pointB[1] == pointC[1] && pointB[0] != pointC[0] && pointD[0] == pointC[0] && pointD[1] == pointA[1] ) { minArea = Math.min(minArea, Math.abs(pointA[1] - pointB[1]) * Math.abs(pointA[0] - pointD[0])); } } } } } return minArea == Integer.MAX_VALUE ? 0 : minArea;
}

Временная сложность O(n^4) из-за 4 вложенных циклов.
Сложность по памяти O(1), т.к. мы не используем никакой дополнительной памяти.

Как можно улучшить это решение?

Можно заметить, что для задания прямоугольника с осями, параллельными осям x и y, достаточно указать всего 2 точки, вместо 4. Для этого достаточно указать координаты точек, лежащих на диагонали, например, A и C. Тогда координаты точек B и D можно вычислить.
Точки A и C образуют диагональ, если их координаты x и y отличаются:

xA != xC
yA != yC

Тогда координаты точек B и D:

B:
xB = xA
yB = yC
D:
xD = xC
yD = yA

Используя этот факт, мы может сократить перебор до 2 вложенных циклов. Мы будем перебирать все пары точек. Для каждой пары точек проверим, образуют ли они диагональ (координаты x и y не равны). Если они образуют диагональ – вычислим координаты точек B и D. Далее нам нужно проверить, если ли точки с такими координатами во входных данных.
Для быстрой проверки нам нужно закешировать все точки в хэш-таблице. В качестве ключа в такой таблице у нас будет “x” кордината точки, а в качестве значения – Set всех “y” координат точек с заданной “x” координатой.
Если точки B и D есть в нашей хэш-таблице, то вычислим его площадь и найдем минимальную площадь.
В коде это выглядит так:

public int minAreaRect(int[][] points) { int minArea = Integer.MAX_VALUE; //Кэшируем все точки  // key - x координата,  //value - множество y координат с фиксированной x координатой HashMap<Integer, Set<Integer>> map = new HashMap<>(); for (int point[] : points) { if (!map.containsKey(point[0])) { map.put(point[0], new HashSet<>()); } map.get(point[0]).add(point[1]); } for (int i = 0; i < points.length; i++) { for (int j = i + 1; j < points.length; j++) { int pointA[] = points[i]; int pointC[] = points[j]; //Если точки A и C образуют диагональ //И в хэш-таблице есть точки B и D if (pointA[0] != pointC[0] && pointA[1] != pointC[1] && map.get(pointA[0]).contains(pointC[1]) && map.get(pointC[0]).contains(pointA[1])) { //Вычисляем площадь и находим минимум minArea = Math.min(minArea, Math.abs(pointA[1] - pointC[1]) * Math.abs(pointA[0] - pointC[0])); } } } return minArea == Integer.MAX_VALUE ? 0 : minArea;
}

Временная сложность O(n^2).
Сложность по памяти O(n) из-за хранения точек в хэш-таблице.