Home » Interview coding problems/challenges

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.
Submitted by Divyansh Jaipuriyar, on September 03, 2020

Problem statement

Given a N*M binary matrix find the size of largest square sub-matrix of 1's present in it.

Problem description:

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.

Input

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.

Output

You need to print the largest square sub-matrix of 1 in separate lines.

Examples

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

Solution Approach

(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.

if(current cell has 1)
    mat[i][j]=1+min(mat[i-1][j],mat[i][j-1],mat[i-1][j-1])
else
    mat[i][j]=0,which ends at here.

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):

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

typedef long long ll;

//declare a matrix
ll mat[1003][1003];

//declare solve function which will
//take three parameters as n,m and res.
ll solve(ll n, ll m, ll& res)
{
    //base case when in first row
    //or in first column.
    if (n == 0 || m == 0) {
        //store maximum value in res.
        res = max(res, mat[n][m]);
        return mat[n][m];
    }
    //largest square-sub matrix in left of
    //current position.
    ll l = solve(n, m - 1, res);

    //largest square-sub matrix in top-left
    //of current position.
    ll lt = solve(n - 1, m - 1, res);

    //largest square-sub matrix in top
    //of current position.
    ll up = solve(n - 1, m, res);

    //declare temporary variable ans.
    ll ans = 0;
    //check if current position has 1 or not
    //if it has 1 then it must be in the largest
    //square-sub matrix.
    if (mat[n][m] != 0)
        ans = 1 + min(min(l, lt), up);

    //store maximum value in res.
    res = max(res, ans);
    return ans;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix N and M: ";
        ll n, m;
        cin >> n >> m;

        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++)
                cin >> mat[i][j];

        ll res = 0;

        solve(n - 1, m - 1, res);

        cout << "Largest size of sub-matrix: ";
        cout << res << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of matrix N and M: 4 4
Enter elements:
1 1 1 1 
1 1 1 1
1 1 1 1
1 1 1 1
Largest size of sub-matrix: 4
Enter size of matrix N and M: 2 2
Enter elements:
1 1 
0 0
Largest size of sub-matrix: 1
Enter size of matrix N and M: 4 4
Enter elements:
0 0 0 0
0 1 1 0 
0 1 1 0
0 0 0 0
Largest size of sub-matrix: 2

C++ Implementation (Dynamic Programming Approach):

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix N and M: ";
        ll n, m;
        cin >> n >> m;

        ll mat[n][m];

        //initialize variable mv with 0.
        ll mv = 0;

        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++) {
                cin >> mat[i][j];
                {
                    if (mat[i][j])
                        mv = 1;
                }
            }
        cout << "Largest size of sub-matrix: ";

        //if there is no 1 then simply print 0.
        if (mv == 0)
            cout << 0 << "\n";
        else {
            //iterate through all elements
            //of the matrix then check for other cases.
            for (ll i = 1; i < n; i++) {
                for (ll j = 1; j < m; j++) {
                    //check if current position is 1 or not.
                    if (mat[i][j]) {
                        //check minimum among other 3 matrix.
                        if (mat[i - 1][j] and mat[i][j - 1] and mat[i - 1][j - 1]) {
                            mat[i][j] = 1 + min(min(mat[i - 1][j], mat[i][j - 1]), mat[i - 1][j - 1]);
                            mv = max(mv, mat[i][j]);
                        }
                    }
                }
            }
            cout << mv << "\n";
        }
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of matrix N and M: 2 2
Enter elements:
1 0
0 1
Largest size of sub-matrix: 1
Enter size of matrix N and M: 2 2
Enter elements:
1 1 
1 1
Largest size of sub-matrix: 2
Enter size of matrix N and M: 3 3
Enter elements:
0 1 1
0 1 1
0 1 1
Largest size of sub-matrix: 2