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

#algorithms #java #google #faang

Задача.

Дан массив точек на плоскости. Нужно найти минимальную площадь прямоугольника образованного этими точками, у которого стороны параллельны оси 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;
}