Problem Statement

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

Problem Link

Maximal Square - LeetCode

Approach

Understanding basics

Reference Video

https://www.youtube.com/watch?v=RElcqtFYTm0&ab_channel=TECHDOSE

Code

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        
        int m = matrix.size();
        int n = matrix[0].size();
        
        int dp[m+1][n+1],largest = 0;
        
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=n;j++)
            {
                if(i==0||j==0)
                    dp[i][j]=0;
                else
                
                    if(matrix[i-1][j-1]=='1')
                        dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1],dp[i-1][j-1]));
                
                else
                     dp[i][j] = 0;
                
                largest = max(largest,dp[i][j]);
            }
        }
      return largest*largest;
   }
};