Saturday 26 December 2020

Maximum size square sub-matrix with all 1s

 

Maximum size square sub-matrix with all 1s

 Approach: Think how you what information you are getting while traversing  the matrix. I find that while traversing the matrix i try to store that how many ones i have encountered  in past. So that is the key of solve the problem, just use your memory/result to get the result. Maximum size square can find as maximum number in the result matrix.

it can used to print the small matrix, but in actual there can be multiple places where you can find the square size coordinates.so returning the maximum size can solve the problem. To get the coordinates we in count how many max size matrix we have then we can try to use it.that coordinates with max square sum.

complexity space:(m*n) time: O(m*n)