Largest sub-square matrix with all 1s Problem

Given a two-dimensional binary matrix, find the largest square submatrix with all 1s.

Example

Input: [

[1, 0, 0],

[0, 1, 1],

[0, 1, 1]

]

Output: 2

The 1s in bold form a square submatrix 2x2 with all 1s. That’s the largest one. Length of its side is 2.

Notes

Input Parameters: There are three arguments, n, m, mat denoting the number of rows, number of columns of the matrix and the two-dimensional matrix of integers.

Output: Return an integer, the length of the side of the largest square submatrix with all 1s.

Constraints:

● 1

Solution

We provided three solutions.

1) brute_force_solution:

In this approach we assume every cell in the matrix as the top-left. We iterate over the matrix and try to see what is the maximum size of the square submatrix with all 1s we can find.

Time Complexity:

O( (n*m)^2) where n is number of rows of matrix and m is number of columns in the input.

To visit each cell and choose it as top-left cell of the square submatrix take O(n*m) time. Now to calculate the maximum size of the square submatrix we start looking if it is feasible for a size 1 matrix, then for size 2 and so on. Next is to check if the corresponding size is possible or not. Since it is possible to have a square submatrix of all 1s for (size-1). So, for a submatrix of size, it can be done by two linear traversal one row wise and another column wise for the last row and last column of the submatrix.

The time complexity for this step is O(min(m,n)) * (2*O(min(m,n)) → O(n*m). Therefore, the total time complexity becomes O(n*m)*O(n*m) → O((m*n)^2).

Auxiliary Space Used:

O(1). Since we are only traversing on the original matrix without storing anything extra.

Space Complexity:

O(n*m) where n is number of rows of matrix and m is number of columns in the input.

For storing input it will take space of O(n*m) and auxiliary space used is O(1).

O(n*m) + O(1) → O(n*m).

// -------- START --------
// @param n: integer n, denoting number of rows of matrix
// @param m: integer m, denoting number of columns of matrix
// @param mat: denoting 2D integer array (matrix) of size n*m
int largest_sub_square_matrix(int n, int m, vector> &mat)
{   
    // stores max size of sub square matrix
    int maxi = 0;

    // iterating on all cells of mat 
    for(int i=0;i

2) other_solution:

In this solution, we approach the problem dynamically. 

Let’s first decide a state for our DP solution. Here we choose state(i, j), which will tell us the maximum size of the square submatrix with all 1s considering the cell (i, j) as the bottom-right most cell of the sub matrix. Now, we see that for a state(i, j), its value can be computed using the below state relation:

state(i, j) = min(state(i, j-1) ,state(i-1, j) ,state(i-1, j-1)) + 1 if mat[i][j] = 1

state(i, j) = 0 otherwise.

Now we just add memorization to the above states, So that we do not calculate the same state more than once. As discussed till now, our DP state will look something like dp[n][m]. But here is one catch. If you observe carefully then to calculate a particular state we only look to its neighbouring 3 states. So, there is no requirement to cache all the state. Will simply cache the corresponding 3 states and it solves our problem. As described in the above state relation, two lookup states belong to the row just above the current state and one state lies in the same row and just in the previous column of the current state. Hence, we will now only maintain a linear memorization table that caches the state solutions of the previous row. The same memorization table is updated every time we calculate a state so that it can be used for the states that belong to the next row. Kindly, refer to the solution for better understanding.

Time Complexity:

O(n*m) where n is number of rows of matrix and m is number of columns of matrix.


As there are a total of m*n states and each state is being calculated only once and to calculate each state me make three lookups. Hence, the time complexity of the dp solution is (number of states) * (number of state lookups) → O(n*m) * 3 → O(m*n).

Auxiliary Space Used:

O(m) where m is the number of columns of the matrix.

As we are storing the dp array of size equal to column of matrix while iterating over matrix.


Space Complexity:

O(n*m) where n is number of rows of matrix and m is number of columns of matrix.


To store input matrix, it will take O(n*m), the size of the given matrix mat and auxiliary space used id O(m).

So, O(n*m) + O(m) → O(n*m).

// -------- START --------
// @param n: integer n, denoting number of rows of matrix
// @param m: integer m, denoting number of columns of matrix
// @param mat: denoting 2D integer array (matrix) of size n*m
int largest_sub_square_matrix(int n, int m, vector> &mat)
{   
    // memoization vector
    vector dp;
    // initializing maximum size of sub square matrix
    int maxi = 0;
    // initializing dp array with first row of matrix mat
    for (int i = 0; i < m; i++) {
        dp.push_back(mat[0][i]);
        maxi = max(maxi, dp[i]);
    }
    int prev = 0;
    int diagonal = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // caching calculated answer for state (i-1, j)
            int tmp = dp[j];

            // if current cell can be a bottom corner
            if (mat[i][j]) {
                if(j != 0)
                    prev = dp[j-1];
                else
                    prev = 0;
                // getting minimum from the below states
                // state (i-1, j-1) ~ diagonal
                // state (i, j-1) ~ prev
                // state (i-1, j) ~ tmp 
                dp[j] = min(min(prev, tmp),diagonal) + 1;
            }
            else {
                dp[j] = 0;
            }
            // caching (i,j-1) ~ tmp state as diagonal for next state
            diagonal = tmp;
            // updating the maximum sub-matrix encounted so far
            maxi = max(maxi, dp[j]);
        }
    }
    return maxi;
}
// -------- END --------
	

3) optimal_solution:

The approach in this solution is the same as the other_solution that uses the same dynamic programming state relation. Here, instead of taking an auxiliary memory we use the provided input matrix to store the DP state and once when all the DP states are computed and we have our answer.

Time Complexity:

O(n*m). Same as other_solution O(n*m) as the algorithm remains the same.


Auxiliary Space Used:

O(1). Since we are using the original input matrix to store DP states.


Space Complexity:

O(n*m) where n is number of rows of matrix and m is number of columns of matrix. For storing input it will take space of O(n*m) and auxiliary space used is O(1).

So, O(n*m) + O(1) → O(n*m).

// -------- START --------
// @param n: integer n, denoting number of rows of matrix
// @param m: integer m, denoting number of columns of matrix
// @param mat: denoting 2D integer array (matrix) of size n*m
int largest_sub_square_matrix(int n, int m, vector> &mat)
{   
    // stores the size of largest square sub matrix
    int maxi = 0;

    // initializing max sub square size "maxi"
    // by checking first row and first column of mat
    for (int i = 0; i < n; i++)
        maxi |= mat[i][0];
    for (int j = 0; j < m; j++)
        maxi |= mat[0][j];

    // populating dp
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (mat[i][j] == 1) {
                // getting minimum from the below states
                // state (i-1, j-1) 
                // state (i, j-1) 
                // state (i-1, j)
                int value = min(mat[i - 1][j - 1],min(mat[i - 1][j], mat[i][j - 1])) + 1;
                // using current matrix state as dp state
                mat[i][j] = value;
                // updating maximum size encountered so far
                maxi = max(mat[i][j], maxi);
            }
        }
    }

    return maxi;
}
// -------- END --------