Largest Square Sub Matrix of 1's in Given Binary Matrix
Given a N*M binary matrix find the size of largest square sub-matrix of 1's present in it.
They want you to find the size of the largest square matrix which have all its elements equal to 1, we need to notice that there are several rectangles which have all its elements equal to 1 but you need to find the square only no rectangle. A square matrix has an equal number of rows and columns.
The first line of input consist of T number of test cases. Each test case consist of size of N and M, each of the following N lines consist of M values either 1 or 0.
You need to print the largest square sub-matrix of 1 in separate lines.
Input: T=1 N=3,M=3 0 1 1 0 1 1 0 1 1 Output: 2 Input: T=1 N=4,M=4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 Output: 2
(a) Recursion Approach:
We will use the logic that a square matrix can be formed only when its top-left, top and left matrix has size one less than the current square matrix, i.e. if we are using (n*n) size matrix then it must have (n-1)*(n-1) matrix in other three parts as discussed earlier.
We will use the recurrence relation: The size of the largest square submatrix ending at cell (i,j) is equal to 1 plus the minimum among the other three parts as (i-1,j), (i,j-1) and (i-1,j-1). The final maximum value will be the maximum among all such a square matrix.
The maximum will be the maximum among all such mat[i][j].
Time complexity for the above approach in the worst case is exponential.
(b) Dynamic Programming Approach:
In this approach we will see the bottom-up approach in which we will initialize our base cases as if there is no 1 in the matrix then the answer is 0 otherwise our answer will be 1 initially, then we iterate through all the matrix position and check if current position if the matrix contains 1 or not if 1 then we check the minimum value among the three other matrices before it and 1 to it. Then we check the maximum value among our max variable and matrix value.
Time complexity for the above case is in the worst case is: O(N*M)
Space complexity for the above case is in the worst case is: O(N*M)
C++ Implementation (Recursion Approach):
C++ Implementation (Dynamic Programming Approach):
Output:need an explanation for this answer? contact us directly to get an explanation for this answer