LeetCode-in-All

221. Maximal Square

Medium

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example 1:

Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]

Output: 4

Example 2:

Input: matrix = [[“0”,”1”],[“1”,”0”]]

Output: 1

Example 3:

Input: matrix = [[“0”]]

Output: 0

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

Solution

/**
 * @param {character[][]} mArr
 * @return {number}
 */
var maximalSquare = function(mArr) {
    if (mArr.length === 0 || mArr[0].length === 0) return 0

    let maxLen = 0
    let rows = mArr.length
    let cols = mArr[0].length
    let dpArr = Array.from({ length: rows }, () => new Array(cols).fill(0))

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (mArr[i][j] === '0') continue
            dpArr[i][j] = 1
            if (i > 0 && j > 0) {
                dpArr[i][j] = Math.min(
                    dpArr[i - 1][j],
                    dpArr[i][j - 1],
                    dpArr[i - 1][j - 1]
                ) + 1
            }
            maxLen = Math.max(maxLen, dpArr[i][j])
        }
    }
    return maxLen * maxLen
};

export { maximalSquare }

This site is open source. Improve this page.