Largest Square Submatrix With All 1s Problem Statement

Given a two-dimensional binary matrix of size n * m, find the largest square submatrix with all 1s.

Example

{
"n": 3,
"m": 3,
"mat": [
[1, 0, 0],
[0, 1, 1],
[0, 1, 1]
]
}

Output:

2

2x2 submatrix at right-bottom has all 1s. That’s the largest one. Length of its side is 2.

Notes

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

Constraints:

• 1 <= n, m <= 1000

We provided three solutions. We will refer to the number of rows and columns in mat by n and m respectively.

Largest Square Submatrix With All 1S Solution 1: Brute Force

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)²).

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)²).

Auxiliary Space Used

O(1).

Since we are only traversing on the original matrix without storing anything extra.

Space Complexity

O(n * m).

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

Code For Largest Square Submatrix With All 1S Solution 1: Brute Force

/*
* Asymptotic complexity in terms of number of rows in \`mat\` \`n\` and number of columns in \`mat\` \`m\`:
* Time: O((n * m)^2).
* Auxiliary space: O(1).
* Total space: O(n * m).
*/

int largest_sub_square_matrix(int n, int m, vector<vector<int>> &mat) {
    int maximum_size = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(!mat[i][j])
                continue;
            // Assuming mat[i][j] as top left corner
            // and checking for all sizes of sub-squre matrix.
            int flag = 1;
            for(int sz = 0; (i + sz) < n && (j + sz) < m; sz++) {
                if(!flag)
                    break;
                for(int col = j; col <= (j + sz); col++) {
                    if(!mat[i + sz][col]) {
                        flag = 0;
                        break;
                    }
                }
                for(int row = i; flag && row <= (i + sz); row++) {
                    if(!mat[row][j + sz]) {
                        flag = 0;
                        break;
                    }
                }
                // Updating the maximum size encountered so far.
                if(flag)
                    maximum_size = max(maximum_size, sz + 1);
            }
        }
    }
    return maximum_size;
}

Largest Square Submatrix With All 1S Solution 2: Other

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

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

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

Space Complexity

O(n * m).

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

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

Code For Largest Square Submatrix With All 1S Solution 2: Other

/*
* Asymptotic complexity in terms of number of rows in \`mat\` \`n\` and number of columns in \`mat\` \`m\`:
* Time: O(n * m).
* Auxiliary space: O(m).
* Total space: O(n * m).
*/

int largest_sub_square_matrix(int n, int m, vector<vector<int>> &mat)
{
    // Memoization table.
    vector<int> dp;

    int maximum_size = 0;
    // Initializing dp array with first row of matrix mat.
    for (int i = 0; i < m; i++) {
        dp.push_back(mat[0][i]);
        maximum_size = max(maximum_size, 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;

            maximum_size = max(maximum_size, dp[j]);
        }
    }
    return maximum_size;
}

Largest Square Submatrix With All 1S Solution 3: Optimal

The approach in this solution is the same as 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).

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

Code For Largest Square Submatrix With All 1S Solution 3: Optimal

/*
* Asymptotic complexity in terms of number of rows in \`mat\` \`n\` and number of columns in \`mat\` \`m\`:
* Time: O(n * m).
* Auxiliary space: O(1).
* Total space: O(n * m).
*/

int largest_sub_square_matrix(int n, int m, vector<vector<int>> &mat)
{
    int maximum_size = 0;

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

    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)
                mat[i][j] = min(mat[i - 1][j - 1], min(mat[i - 1][j], mat[i][j - 1])) + 1;

                maximum_size = max(mat[i][j], maximum_size);
            }
        }
    }

    return maximum_size;
}

We hope that these solutions to maximal square problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.