(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