Skip to content

17.23. Max Black Square

Description

Imagine you have a square matrix, where each cell (pixel) is either black or white Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Return an array [r, c, size], where r, c are the row number and the column number of the subsquare's upper left corner respectively, and size is the side length of the subsquare. If there are more than one answers, return the one that has smallest r. If there are more than one answers that have the same r, return the one that has smallest c. If there's no answer, return an empty array.

Example 1:


Input:

[

  [1,0,1],

  [0,0,1],

  [0,0,1]

]

Output: [1,0,2]

Explanation: 0 represents black, and 1 represents white, bold elements in the input is the answer.

Example 2:


Input:

[

  [0,1,1],

  [1,0,1],

  [1,1,0]

]

Output: [0,0,1]

Note:

  • matrix.length == matrix[0].length <= 200

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix)
        down = [[0] * n for _ in range(n)]
        right = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if matrix[i][j] == 0:
                    down[i][j] = down[i + 1][j] + 1 if i + 1 < n else 1
                    right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
        for k in range(n, 0, -1):
            for i in range(n - k + 1):
                for j in range(n - k + 1):
                    if (
                        down[i][j] >= k
                        and right[i][j] >= k
                        and right[i + k - 1][j] >= k
                        and down[i][j + k - 1] >= k
                    ):
                        return [i, j, k]
        return []

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] findSquare(int[][] matrix) {
        int n = matrix.length;
        int[][] down = new int[n][n];
        int[][] right = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (matrix[i][j] == 0) {
                    down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int k = n; k > 0; --k) {
            for (int i = 0; i <= n - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                        && down[i][j + k - 1] >= k) {
                        return new int[] {i, j, k};
                    }
                }
            }
        }
        return new int[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> findSquare(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int down[n][n];
        int right[n][n];
        memset(down, 0, sizeof(down));
        memset(right, 0, sizeof(right));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (matrix[i][j] == 0) {
                    down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int k = n; k > 0; --k) {
            for (int i = 0; i <= n - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k && down[i][j + k - 1] >= k) {
                        return {i, j, k};
                    }
                }
            }
        }
        return {};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func findSquare(matrix [][]int) []int {
    n := len(matrix)
    down := make([][]int, n)
    right := make([][]int, n)
    for i := range down {
        down[i] = make([]int, n)
        right[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if matrix[i][j] == 0 {
                down[i][j], right[i][j] = 1, 1
                if i+1 < n {
                    down[i][j] += down[i+1][j]
                }
                if j+1 < n {
                    right[i][j] += right[i][j+1]
                }
            }
        }
    }
    for k := n; k > 0; k-- {
        for i := 0; i <= n-k; i++ {
            for j := 0; j <= n-k; j++ {
                if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
                    return []int{i, j, k}
                }
            }
        }
    }
    return []int{}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function findSquare(matrix: number[][]): number[] {
    const n = matrix.length;
    const down: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    const right: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = n - 1; j >= 0; --j) {
            if (matrix[i][j] === 0) {
                down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
                right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
            }
        }
    }
    for (let k = n; k > 0; --k) {
        for (let i = 0; i <= n - k; ++i) {
            for (let j = 0; j <= n - k; ++j) {
                if (
                    down[i][j] >= k &&
                    right[i][j] >= k &&
                    right[i + k - 1][j] >= k &&
                    down[i][j + k - 1] >= k
                ) {
                    return [i, j, k];
                }
            }
        }
    }
    return [];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    func findSquare(_ matrix: [[Int]]) -> [Int] {
        let n = matrix.count
        var down = Array(repeating: Array(repeating: 0, count: n), count: n)
        var right = Array(repeating: Array(repeating: 0, count: n), count: n)

        for i in stride(from: n - 1, through: 0, by: -1) {
            for j in stride(from: n - 1, through: 0, by: -1) {
                if matrix[i][j] == 0 {
                    down[i][j] = (i + 1 < n) ? down[i + 1][j] + 1 : 1
                    right[i][j] = (j + 1 < n) ? right[i][j + 1] + 1 : 1
                }
            }
        }

        for k in stride(from: n, through: 1, by: -1) {
            for i in 0...(n - k) {
                for j in 0...(n - k) {
                    if down[i][j] >= k && right[i][j] >= k &&
                       right[i + k - 1][j] >= k && down[i][j + k - 1] >= k {
                        return [i, j, k]
                    }
                }
            }
        }

        return []
    }
}

Comments