Maximum Area of the Square Submatrix

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

The maximum area of the square submatrix problem is one of the most straightforward problems that fall under the dynamic programming regime. Such problems can be seen in many competitive coding contests and coding round interviews in big product-based companies. The problem is easy but coming up with an efficient solution with optimized complexities is the tricky part. But do not worry because this article will surely help you come up with a good solution. 

This article covers the problem of the maximum area of the square submatrix. In this problem, we have been given a matrix, and we have to find out the area of the maximum square in the sub-matrix. It can be done in many ways, but the most efficient way is using dynamic programming. 

The maximum area of the square submatrix

In this problem, we have been given a binary matrix (matrix containing only 0’s and 1’s). Our task is to find out the largest square formed by the 1’s present in the matrix. The problem can be solved in many ways, but the most efficient way to solve the problem is using dynamic programming. While solving the problem, we will come across many overlapping solutions, and computing them multiple times will make our code less efficient. Thus to avoid multiple overlapping solutions, we apply dynamic programming and create a table that contains the size of the largest square that can be formed in the sub-matrix containing all 1’s. 

Problem statement

We have been given a binary matrix of R x C. we have to find the maximum area of the square submatrix.  

For example, if the given array is:

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 1 1 1 0 0

0 0 1 1 1 0 0

0 0 1 1 1 0 0

0 0 0 0 0 0 0

then the largest  sub-matrix square is:

1 1 1

1 1 1

1 1 1

and its area is 3*3 = 9

Approach 

To solve this problem, we apply the concepts of dynamic programming. We create a solution matrix Sol which contains the size of the square formed. We then traverse the whole solution matrix once to find out the maximum value. This maximum value is the size of the square that can be created. Since the area of a square is Side2, thus we square the maximum value and display it.

To simplify the approach,

Step 1: Construct a solution array, Sol, of size R x C.

Step 2: Copy the elements of the first row and first column of Mat into Sol.

Step 3: Traverse Mat and check if Mat[i][j] == 1 or not

  1. If it is 1 then, Sol[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
  2. Else Sol[i][j] == 0
     

Step 4: Traverse Sol to find the maximum element present in the matrix

Step 5: Square the value and display it.

(optional) Step 6:  Using the maximum element value, print the matrix such that the square is displayed. 

The expression in Step 3 helps us determine the maximum size of the square formed in the sub-matrix. We first search for a 1 in the input matrix; keeping that 1 as the top-left corner we start traversing towards the bottom right. We do so to find the maximum size of the square that can be formed. Whenever we encounter a 0, we just fill 0 in the Sol table since we are concerned with 1’s only. We traverse the whole grid and when Sol[i][j] == 0, then no square will be able to contain this cell. If Sol[i][j] == 1, we will have Sol[i][j] = 1 + min(Sol[i-1][j], Sol[i][j-1], Sol[i-1][j-1]), which means that the square will be limited by its left, upper and upper-left neighbors.

Input Matrix:

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 1 1 1 0 0

0 0 1 1 1 0 0

0 0 1 1 1 0 0

0 0 0 0 0 0 0

Sol Matrix:

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 1 1 1 0 0

0 0 1 2 2 0 0

0 0 1 2 3 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

Recommended: Try this problem by clicking here: Maximum Area Square on our CodeStudio - The best platform to prepare for coding interviews before seeing the solution.

Code

#include <iostream>
#define bool int
#define R 7 //number of rows
#define C 7 //number of columns
using namespace std;

int max_i, max_j, max_s;

//function to print the matrix
void printMatrix(bool Mat[R][C]){

    for(int i = max_i; i > max_i - max_s; i--)
    {
        for(int j = max_j; j > max_j - max_s; j--)
        {
            cout << Mat[i][j] << " ";
        }
        cout << "\n";
    }
}

 
//function to find the maximum sub-matrix square
void findMaxSubSq(bool Mat[R][C])
{
    int i,j,area;
    int Sol[R][C]; //solution matrix

    for(i = 0; i < R; i++)
        Sol[i][0] = Mat[i][0];

    for(j = 0; j < C; j++)
        Sol[0][j] = Mat[0][j];

    for(i = 1; i < R; i++)
    {
        for(j = 1; j < C; j++)
        {
            if(Mat[i][j])
                Sol[i][j] = min(Sol[i][j-1],min( Sol[i-1][j],
                                Sol[i-1][j-1])) + 1;
            else
                Sol[i][j] = 0;
        }
    }
    max_s = Sol[0][0]; max_i = 0; max_j = 0;
    for(i = 0; i < R; i++)
    {
        for(j = 0; j < C; j++)
        {
            if(max_s < Sol[i][j])
            {
                max_s = Sol[i][j];
                max_i = i;
                max_j = j;
            }
        }            
    } 
    
    area = max_s*max_s; //finding the area of the largest square
    cout << "The largest square found has sides of "<< max_s << " units." << endl;
    cout << "Area of the square is " << max_s << " * " << max_s << " = " << area << endl;

cout<<"The maximum square sub-matrix is: \n";
printMatrix(Mat);   
}


int main()
{
    bool Mat1[R][C] ={{0000000},
                      {0000000},
                      {0011100},
                      {0011100},
                      {0011100},
                      {0000000}};
                    
    findMaxSubSq(Mat1);
    printf("\n\n");
    
    bool Mat2[R][C] ={{0001000},
                     {0100010},
                     {0111100},
                      {0111100},
                     {0111100},
                     {0111110}};
    
    findMaxSubSq(Mat2);
    
    return 0;
    
}

Output

On running the above code, we get:

The largest square found has sides of 3 units.
Area of the square is 339
The maximum square sub-matrix is:
1 1 1
1 1 1
1 1 1


The largest square found has sides of 4 units.
Area of the square is 4416
The maximum square sub-matrix is:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Complexity Analysis 

Time complexity

In the given implementation, we traverse the whole matrix to find the maximum square in the sub-matrix. Thus time complexity is,

T(n) = O(R*C),

Where R is the number of rows of our matrix and C is the number of Columns of our matrix

Space complexity

In the given implementation, we store a solution matrix Sol[][] of R rows and C columns which contains the size of the squares formed in the sub-matrix. Thus,

Space Complexity = O(R*C),

Where R is the number of rows of our matrix and C is the number of Columns of our matrix

Frequently Asked Questions

Q1. What does Dynamic Programming mean?
Dynamic Programming or DP is a specialized algorithm paradigm in the field of computer science. In this technique, we solve an optimization problem by breaking it down into simpler subproblems. We do so by keeping in mind that the optimal solution to the overall problem depends on optimal subproblem solutions.

Key Takeaways

To summarize, this article discusses the problem - The maximum area of the square submatrix. We first discussed the problem briefly, the problem statement, the approach used in this article, followed by the solution code.

Learn more about Data Structures and Algorithms through this course: Basics of C++ with Data Structures and Algorithms.

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.  

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think