Сложность: hard
Задача: 302. Smallest Rectangle Enclosing Black Pixels

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

👨‍💻 Алгоритм:

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    minArea(image, x, y) {
        const m = image.length, n = image[0].length;
        const left = this.searchColumns(image, 0, y, 0, m, true);
        const right = this.searchColumns(image, y + 1, n, 0, m, false);
        const top = this.searchRows(image, 0, x, left, right, true);
        const bottom = this.searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

    searchColumns(image, i, j, top, bottom, opt) {
        while (i !== j) {
            const k = Math.floor((i + j) / 2);
            let t = top;
            while (t < bottom && image[t][k] === '0') t++;
            if ((t < bottom) === opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }

    searchRows(image, i, j, left, right, opt) {
        while (i !== j) {
            const k = Math.floor((i + j) / 2);
            let l = left;
            while (l < right && image[k][l] === '0') l++;
            if ((l < right) === opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }
}

Ставь 👍 и забирай 📚 Базу знаний