Maximum Area Square

Moderate

0/80

Average time to solve is 10m

12 upvotes

Asked in companies

Problem statement

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:

The area of the largest square submatrix with all 1s is 4.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

Explanation of the Sample Input 1:

For the given grid, the largest square with all 1s has a side of length 1. So, the area will be 1 * 1 = 1.

Sample Input 2:

Sample Output 2:

4
1

Console