Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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 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][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.