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
If it is 1 then, Sol[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 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 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.
The largest square found has sides of 3 units. Area of the square is 3 * 3 = 9 The maximum square sub-matrix is: 111 111 111
The largest square found has sides of 4 units. Area of the square is 4 * 4 = 16 The maximum square sub-matrix is: 1111 1111 1111 1111
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.
305+ registered