DEV Community

faangmaster
faangmaster

Posted on

2

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

Задача.

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

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

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

Image description

Ссылка на 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
Enter fullscreen mode Exit fullscreen mode

Image description

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

S = |yB - yA| * |xD - xA|
Enter fullscreen mode Exit fullscreen mode

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

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;
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

xA != xC
yA != yC
Enter fullscreen mode Exit fullscreen mode

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

B:
xB = xA
yB = yC
D:
xD = xC
yD = yA
Enter fullscreen mode Exit fullscreen mode

Image description

Используя этот факт, мы может сократить перебор до 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;
}
Enter fullscreen mode Exit fullscreen mode

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more