Maximal Square

Problem Statement:

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

The trick here is to think in terms of side length of the proposed maximum square. lets say we know the maximum square length of matrix of size i , j-1 Now we insert the jth element in the ith row. this can either increase the side length of the proposed square or it may remain the same.

Say the element at index i , j is zero then it cannot be part of any square with 1 so we skip that index otherwise that index can be a part of some square .

Now element at i, j-1 and i-1,j , i-1,j-1also give us the maximum side length ending at that index . Any square ending at i ,j may have as subsquares squares ending at index i — 1, j-1 , i , j-1 or j -1, i so the proposed side length of square ending at i ,j should be minimum of all these indices

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.