221_Maximal_Square

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


// DYNAMIC PROGRAMMING APPROACH
class Solution {
    public int maximalSquare(char[][] matrix){
        int rows = matrix.length;
        int cols = rows>0?matrix[0].length:0;
        int dp[][] = new int[rows+1][cols+1];
        int maxsofar = 0;
        for(int i=1;i<=rows;i++)
        {
            for(int j=1;j<=cols;j++)
            {
                if(matrix[i-1][j-1]=='1')
                {
                    dp[i][j] = Math.min(((int)Math.min(dp[i][j-1],dp[i-1][j-1])),dp[i-1][j])+1;
                    if(maxsofar<dp[i][j])
                        maxsofar = dp[i][j];
                }
            }
        }
        return maxsofar*maxsofar;
    }
}
    
//      BRUTE FORCE APPROACH    
//     public int maximalSquare(char[][] matrix) {
//         int maxsqlen = 0;
//         int rows = matrix.length;int cols = rows>0?matrix[0].length:0;
//         for(int i=0;i<rows;i++)
//         {
//             for(int j=0;j<cols;j++)
//             {
//                 if(matrix[i][j]=='1')
//                 {
//                     int sqlen = 1;
//                     boolean flag = true;
//                     while(sqlen+i<rows && sqlen+j<cols && flag)   
//                     {
//                         for(int k=j;k<=j+sqlen;k++)
//                         {
//                             if(matrix[i+sqlen][k]=='0'){
//                                 flag = false;
//                                 break;
//                             }
//                         }
//                         for(int k=i;k<=i+sqlen;k++)
//                         {
//                             if(matrix[k][j+sqlen]=='0')
//                             {
//                                 flag = false;
//                                 break;
//                             }
//                         }
//                         if(flag)
//                             sqlen++;
//                     }
//                     if(maxsqlen<sqlen)
//                         maxsqlen = sqlen;
//                 }
//             }
//         }
//         return maxsqlen*maxsqlen;
//     }
// }