s0221_maximal_square

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[][]} matrix
# @return {Integer}
def maximal_square(matrix)
  m = matrix.length
  return 0 if m == 0

  n = matrix[0].length
  return 0 if n == 0

  dp = Array.new(m + 1) {Array.new(n + 1, 0)}
  max = 0

  (0...m).each do |i|
    (0...n).each do |j|
      if matrix[i][j] == '1'
        # 1 + minimum from cell above, cell to the left, cell diagonal upper-left
        next_val = 1 + [dp[i][j], [dp[i + 1][j], dp[i][j + 1]].min].min
        # keep track of the maximum value seen
        max = [max, next_val].max
        dp[i + 1][j + 1] = next_val
      end
    end
  end

  max * max
end