Maximal Square | Problems

You're given an m x n matrix of 1s and 0s. Find the largest square-shaped block made entirely of 1s and return its area.

Input Format

Implement maximalSquare(matrix). Inputs below show JavaScript function arguments; there is no stdin parsing.

Output Format

Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input

matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output

Example 2

Input

matrix = [["0","1"],["1","0"]]

Output

Constraints

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

Test Cases (2)

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.

javascript

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.