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

Hint 1

Hint 2

Hint 3

Try to use the prefix sum of the matrix.

Approaches (3)

Approach 1

Approach 2

Approach 3

Naive Approach

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.

Time Complexity

O(N * M * min(N, M)), where N is the number of rows in the given grid, and M is the number of columns.

Since we are iterating the whole grid once for every possible side of the square. Hence, the time complexity is O(N * M * min(N, M)).

Space Complexity

O(1), i.e. constant space complexity.

(100% EXP penalty)

Maximum Area Square

Console