Maximum Area of the Square Submatrix
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 productbased 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 submatrix. 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 submatrix 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 submatrix 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 Side^{2}, 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
 If it is 1 then, Sol[i][j] = min(S[i][j1], S[i1][j], S[i1][j1]) + 1
 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 submatrix. We first search for a 1 in the input matrix; keeping that 1 as the topleft 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[i1][j], Sol[i][j1], Sol[i1][j1]), which means that the square will be limited by its left, upper and upperleft 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>

Output
On running the above code, we get:
The largest square found has sides of 3 units. Area of the square is 3 * 3 = 9 The maximum square submatrix is: 1 1 1 1 1 1 1 1 1 The largest square found has sides of 4 units. Area of the square is 4 * 4 = 16 The maximum square submatrix 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 submatrix. 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 submatrix. 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.
Comments
No comments yet
Be the first to share what you think