221. Maximal Square

Problem

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 (Java)

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    // 1 + minimum from cell above, cell to the left, cell diagonal upper-left
                    int next = 1 + Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]));
                    // keep track of the maximum value seen
                    if (next > max) {
                        max = next;
                    }
                    dp[i + 1][j + 1] = next;
                }
            }
        }
        return max * max;
    }
}

Solution (Javascript)

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
  var m = matrix.length;
  var n = (matrix[0] || []).length;
  var dp = Array(m).fill(0).map(_ => Array(n));
  var max = 0;

  for (var k = 0; k < m; k++) {
    dp[k][0] = matrix[k][0] === '1' ? 1 : 0;
    max = Math.max(max, dp[k][0]);
  }

  for (var p = 0; p < n; p++) {
    dp[0][p] = matrix[0][p] === '1' ? 1 : 0;
    max = Math.max(max, dp[0][p]);
  }

  for (var i = 1; i < m; i++) {
    for (var j = 1; j < n; j++) {
      if (matrix[i][j] === '1') {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
        max = Math.max(max, dp[i][j]);
      } else {
        dp[i][j] = 0;
      }
    }
  }

  return max * max;
};

Explain:

nope.

Complexity:

• Time complexity : O(m*n).
• Space complexity : O(m*n).