← Static tasks

302. Smallest Rectangle Enclosing Black Pixels

leetcode hard

#backtracking#csharp#hard#leetcode#matrix#search#string#two-pointers

Task

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.

Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.

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

C# solution

matched/original
public class Solution {
    public int MinArea(char[][] image, int x, int y) {
        int m = image.Length, n = image[0].Length;
        int left = SearchColumns(image, 0, y, 0, m, true);
        int right = SearchColumns(image, y + 1, n, 0, m, false);
        int top = SearchRows(image, 0, x, left, right, true);
        int bottom = SearchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }
    private int SearchColumns(char[][] image, int i, int j, int top, int bottom, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int t = top;
            while (t < bottom && image[t][k] == '0') t++;
            if ((t < bottom) == opt) {
                j = k;
            } else {
               ### Go
```go
package main
func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    left := searchColumns(image, 0, y, 0, m, true)
    right := searchColumns(image, y+1, n, 0, m, false)
    top := searchRows(image, 0, x, left, right, true)
    bottom := searchRows(image, x+1, m, left, right, false)
    return (right - left) * (bottom - top)
}
func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        t := top
        for t < bottom && image[t][k] == '0' {
            t++
        }
        if (t < bottom) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}
func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        l := left
        for l < right && image[k][l] == '0' {
            l++
        }
        if (l < right) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinArea(char[][] image, int x, int y) {
        int m = image.size(), n = image[0].size();
        int left = SearchColumns(image, 0, y, 0, m, true);
        int right = SearchColumns(image, y + 1, n, 0, m, false);
        int top = SearchRows(image, 0, x, left, right, true);
        int bottom = SearchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }
    private int SearchColumns(char[][] image, int i, int j, int top, int bottom, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int t = top;
            while (t < bottom && image[t][k] == '0') t++;
            if ((t < bottom) == opt) {
                j = k;
            } else {
               ### Go
```go
package main
func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    left := searchColumns(image, 0, y, 0, m, true)
    right := searchColumns(image, y+1, n, 0, m, false)
    top := searchRows(image, 0, x, left, right, true)
    bottom := searchRows(image, x+1, m, left, right, false)
    return (right - left) * (bottom - top)
}
func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        t := top
        for t < bottom && image[t][k] == '0' {
            t++
        }
        if (t < bottom) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}
func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        l := left
        for l < right && image[k][l] == '0' {
            l++
        }
        if (l < right) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

Java solution

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

    private int searchColumns(char[][] image, int i, int j, int top, int bottom, boolean whiteToBlack) {
        while (i != j) {
            int k = top, mid = (i + j) / 2;
            while (k < bottom && image[k][mid] == '0') ++k;
            if (k < bottom == whiteToBlack)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }

    private int searchRows(char[][] image, int i, int j, int left, int right, boolean whiteToBlack) {
        while (i != j) {
            int k = left, mid = (i + j) / 2;
            while (k < right && image[mid][k] == '0') ++k;
            if (k < right == whiteToBlack)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
}

JavaScript solution

matched/original
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;
    }
}

Python solution

matched/original
class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        left = self.searchColumns(image, 0, y, 0, m, True)
        right = self.searchColumns(image, y + 1, n, 0, m, False)
        top = self.searchRows(image, 0, x, left, right, True)
        bottom = self.searchRows(image, x + 1, m, left, right, False)
        return (right - left) * (bottom - top)

    def searchColumns(self, image: List[List[str]], i: int, j: int, top: int, bottom: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = top, (i + j) // 2
            while k < bottom and image[k][mid] == '0':
                k += 1
            if (k < bottom) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

    def searchRows(self, image: List[List[str]], i: int, j: int, left: int, right: int, whiteToBlack: bool) -> int:
        while i != j:
            k, mid = left, (i + j) // 2
            while k < right and image[mid][k] == '0':
                k += 1
            if (k < right) == whiteToBlack:
                j = mid
            else:
                i = mid + 1
        return i

Go solution

matched/original
package main

func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    left := searchColumns(image, 0, y, 0, m, true)
    right := searchColumns(image, y+1, n, 0, m, false)
    top := searchRows(image, 0, x, left, right, true)
    bottom := searchRows(image, x+1, m, left, right, false)
    return (right - left) * (bottom - top)
}

func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        t := top
        for t < bottom && image[t][k] == '0' {
            t++
        }
        if (t < bottom) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        l := left
        for l < right && image[k][l] == '0' {
            l++
        }
        if (l < right) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

Explanation

Algorithm

Пример

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

Output: 6

👨‍💻

Алгоритм:

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

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

left = min(left, x)

right = max(right, x + 1)

top = min(top, y)

bottom = max(bottom, y + 1)

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

😎