Maximal Square

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 = {{'0','1'},{'1','0'}}
Output: 1

Approach

Java

public class MaximalSquare {
    public static void main(String[] args) {
        char matrix[][] = { { '0', '1' }, { '1', '0' } };
        System.out.println(maximalSquare(matrix));
    }

    static int maximalSquare(char[][] matrix) {
        int n = matrix.length;
        if (n == 0)
            return 0;
        int m = matrix[0].length;
        int res = 0;
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j],
                         dp[i - 1][j - 1])) + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int maximalSquare(vector<vector<char>>& matrix)
{
    int n=matrix.size();
    if(n==0)
         return 0;
    int m=matrix[0].size();
    int res=0;
    int dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) 
            {
                if(matrix[i-1][j-1]=='1')
                {
                       dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
                       res=max(res,dp[i][j]);
                }
            }
        }
        return res*res;
}
int main()
{
    vector<vector<char>> matrix = {{'0','1'},{'1','0'}};
    cout<<maximalSquare(matrix);
    return 0;
}