Maximal Square | Problems

Given an m×n binary matrix, find the largest square containing only 1's and return its area.

Example: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] → Output: 4

Sample Input

—

Sample Output

—

Constraints

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

Test Cases

Case 1

Args: [[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]] Expected: 4

Case 2

Args: [[["0","1"],["1","0"]]] Expected: 1

Topics

Dynamic Programming Memoization

Approach: Dynamic Programming

dp[i][j] represents the side length of the largest square whose bottom-right corner is at (i,j). If matrix[i][j] is '1', dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The answer is the maximum dp value squared.

function maximalSquare(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const dp = Array.from({length: m + 1}, () => 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], dp[i][j-1], dp[i-1][j-1]) + 1;
        max = Math.max(max, dp[i][j]);
      }
  return max * max;
}

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Saved in this browser only. Private to you.