Maximum Area Square

Posted: 16 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given a non-empty grid ‘MAT’ consisting of only 0s and 1s. Your task is to find the area of maximum size square sub-matrix with all 1s.

If there is no such sub-matrix, print 0.

For example, for the following grid:

Input

The area of the largest square submatrix with all 1s is 4.
Input Format:
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two space-integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

From the second line of each test case, the next N lines represent the rows of the grid. Every row contains M single space-separated integers.
Output Format:
For each test case, print the area of maximum size square sub-matrix with all 1s. 

Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 50
1 <= M <= 50
0 <= MAT[i][j] <= 1

Time limit: 1 sec
Approach 1

We will check for each length of the square that can be possible in the grid. The maximum length of the square that can be possible in the grid is min(N, M).

 

We will use the prefix sum of the grid to calculate the sum of elements of a submatrix in constant time. 

Try Problem