Maximum size square sub-matrix

Method 1

#include <bits/stdc++.h>
#define R 6
#define C 5
using namespace std;

void printMaxSubMatrix(int matrix[R][C])
{
    int i,j;
    int sum[R][C];
    int maxSum, max_row, max_col;
    //Copying first row and column
    for(i = 0; i < R; i++)
        sum[i][0] = matrix[i][0];
    for(j = 0; j < C; j++)
        sum[0][j] = matrix[0][j];
    //Constructing other entries of S[][]
    for(i = 1; i < R; i++)
    {
        for(j = 1; j < C; j++)
        {
            if(matrix[i][j] == 1)
                sum[i][j] = min({sum[i][j-1], sum[i-1][j], sum[i-1][j-1]}) + 1;
            else
                sum[i][j] = 0;
        }
    }
    //Finding maximum entry from sum[][] matrix an indexes also
    maxSum = sum[0][0]; max_row = 0; max_col = 0;
    for(i = 0; i < R; i++)
    {
        for(j = 0; j < C; j++)
        {
            if(maxSum < sum[i][j])
            {
                maxSum = sum[i][j];
                max_row = i;
                max_col = j;
            }
        }
    }
    //Printing the square maximum submatrix
    cout<<"Maximum size square sub-matrix is: \n";
    for(i = max_row; i > max_row - maxSum; i--)
    {
        for(j = max_col; j > max_col - maxSum; j--)
        {
            cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }
}
int main()
{
    int matrix[R][C] = {{0, 1, 1, 0, 1},
                    {1, 1, 1, 1, 0},
                    {1, 1, 1, 1, 0},
                    {1, 1, 1, 1, 0},
                    {1, 1, 1, 1, 1},
                    {0, 0, 0, 0, 0}};
    printMaxSubMatrix(matrix);
}

You can also try this code with Online C++ Compiler

Run Code

Output :

Maximum size square sub-matrix:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

You can also try this code with Online C++ Compiler

Run Code

The program to find square maximum submatrix of all 1’s has time complexity O(m*n) and space complexity is also O(m*n). Here m represents the number of rows and n number of columns, respectively.

Also read, Application of Oops

Method 2

We can optimize our solution of finding the square maximum submatrix by reducing the space complexity. We need only the current row and previous row to compute an entry in the matrix.

#include <bits/stdc++.h>
using namespace std;
#define R 6
#define C 5

void printMaxSubMatrix(int M[R][C])
{
    int sum[2][C], MaxValue = 0;
    memset(sum, 0, sizeof(sum));    //Initializing sum matrix with 0

    // Construct the entries
    for (int i = 0; i < R;i++)
        for (int j = 0; j < C;j++){
            //Current entry computation
            int entry = M[i][j];
            if(entry)
                if(j)
                    entry = 1 + min(sum[1][j - 1], min(sum[0][j - 1], sum[1][j]));

            // Save last entry and add new entry
            sum[0][j] = sum[1][j];
            sum[1][j] = entry;

            //Track for maximum length
            MaxValue = max(MaxValue, entry);
        }

    //Printing the square maximum submatrix
    cout << "Maximum size square sub-matrix: \n";
    for (int i = 0; i < MaxValue; i++)
    {
        for (int j = 0; j < MaxValue;j++)
            cout << "1 ";
        cout <<endl;
    }
}

int main ()
{
    int matrix[R][C] = {{0, 1, 1, 0, 1},
                    {1, 1, 1, 1, 0},
                    {1, 1, 1, 1, 0},
                    {1, 1, 1, 1, 0},
                    {1, 1, 1, 1, 1},
                    {0, 0, 0, 0, 0}};
    printMaxSubMatrix(matrix);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Maximum size square sub-matrix:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

You can also try this code with Online C++ Compiler

Run Code

Time complexity is the same as the previous code to find maximum submatrix, i.e., O(m*n), but space complexity is reduced to O(n). Here n is the number of columns and m number of rows, respectively.

Try and compile by yourself with the help of online C++ Compiler for better understanding.

Check out this problem - Two Sum Problem

FAQs

1. What does the memset function do?
   Memset function is used to initialize the sum matrix with all entries as 0 in the program to find the square maximum submatrix of all 1’s.
    
2. What is a binary matrix?
   A binary matrix is a two dimensional array with entries as 0 or 1 only.

Key Takeaways

In this article, we have extensively discussed the methods to find a maximum square submatrix with all 1's from a given matrix and its implementation in C++. The blog contains the algorithm to find the maximum submatrix of all 1’s and different approaches to achieve the result.

We hope that this blog has helped you enhance your knowledge regarding maximum submatrix and if you would like to learn more, check out our articles on the Maximum Area of the Square Submatrix in C++. Do upvote our blog to help other ninjas grow. Happy Coding!