Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4

Solution

Its a matrix DP problem, Maintain state matrix based on previous states.

If current element having value as 1 then it could be part of matrix, Possible size of the square matrix ending at the current element could be :

Min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
Code

Output

4

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *