Leetcode: Maximal Square

Maximal Square



Similar Problems:


Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/maximal-square
// Basic Ideas: dynamic programming
// dp[i][j]: length of the rectangle
//    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
//
// We can do it with one pass
// Let's assume we can change the original matrix
// Thus we don't need extra space
//
// Complexity: Time O(n*m), Space O(1)
func maximalSquare(matrix [][]byte) int {
    row_count := len(matrix)
    if row_count == 0 { return 0 }
    col_count := len(matrix[0])
    res := 0
    // initialize counter for corner case
    for i:=0; i<row_count; i++ {
        if matrix[i][0] == '1' { res = 1 }
    }
    for j:=0; j<col_count; j++ {
        if matrix[0][j] == '1' { res = 1 }
    }
    for i:=1; i<row_count; i++ {
        for j:=1; j<col_count; j++ {
            if (matrix[i][j] == '1') {
                v := int(matrix[i-1][j-1])-48
                if v>int(matrix[i-1][j])-48 { v=int(matrix[i-1][j])-48 }
                if v>int(matrix[i][j-1])-48 { v=int(matrix[i][j-1])-48 }
                v += 1
                matrix[i][j] = byte(v+48)
                if v > res { res = v }
            }
        }
    }
    return res*res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.