[Leetcode] 221. Maximal Square

https://leetcode.com/problems/maximal-square/

Maximal Square - LeetCode

 

1. 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.

 

2. Algorithm

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) return 0;
        
        int maxSquareSize = 0;
        int row = matrix.length, col = matrix[0].length;
        int dp[][] = new int[row+1][col+1];
       
        for(int rowIndex = 1; rowIndex <= row; rowIndex++)
        {
            for(int colIndex = 1; colIndex <= col; colIndex++) 
            {
                if(matrix[rowIndex-1][colIndex-1] == '1') {
                    dp[rowIndex][colIndex] = Math.min( dp[rowIndex][colIndex-1],
                        Math.min(dp[rowIndex-1][colIndex-1], dp[rowIndex-1][colIndex]))+1;
                    maxSquareSize = Math.max(maxSquareSize, dp[rowIndex][colIndex]);
                }
            }
        }
        
        return maxSquareSize*maxSquareSize;
    }
}

 

3. retrospective