Leetcode•Apr 06, 2025
221 Maximal Square
Hazrat Ali
Leetcode
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
* Maximal Square
*
* Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
*
* Example:
*
* Input:
*
* 1 0 1 0 0
* 1 0 1 1 1
* 1 1 1 1 1
* 1 0 0 1 0
*
* Output: 4
*/
Solution
/**
* @param {character[][]} matrix
* @return {number}
*/
const maximalSquare = matrix => {
if (!matrix || matrix.length === 0) {
return 0;
}
const m = matrix.length;
const n = matrix[0].length;
const dp = Array(m + 1);
for (let i = 0; i <= m; i++) {
dp[i] = Array(n + 1).fill(0);
}
let max = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] === '1') {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max * max;
};