Maximum size subrectangle

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in company
Adobe

Problem statement

You are given an 'N' * 'M' size binary-valued matrix, where 'N' is the number of rows and 'M' is the number of columns.

Your task is to return the size (area) of the maximum size submatrix which consists of all 1s i.e. the maximum area of a submatrix in which each cell has only the value ‘1’.

Note:
1. Binary-valued matrix has either 0 or 1 in each cell.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.

subMatrix_image

In the above image, areas in green, red, and violet colour are all submatrices of the original 4x4 matrix.

3. The area of a matrix with 'H' rows and 'W' columns is equal to 'H' * 'W'. 
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two space-separated integers 'N' and 'M'.

Then each of the next 'N' lines of each test case contains 'M' space-separated integers(either 1 or 0).
Output Format:
Print the area of maximum size submatrix of all 1s in the given matrix.

Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N, M <= 100

Time Limit: 1 sec
Sample Input 1:
1
5 4
1 0 1 1
1 0 1 1
0 1 0 1
1 1 1 1
0 0 0 1
Sample Output 1:
5
Explanation for Sample Input 1:

explanationSampleInput1

Sample Input 2:
1
4 4
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
Sample Output 2:
8
Hint

Can you use the “Largest rectangle in a histogram” technique to calculate the area?

Approaches (2)
Largest Rectangle in a Histogram
  • The trick is to maintain a data structure that could mimic the function of the monotone increasing queue, which a stack can perform.
  • Suppose you have an input array height[0], height[1], height[2] ….,height[N-1].
    • Let’s suppose that we are at some index j, then we try to fix height[j] as the right side of the rectangle, then any of the heights { height[0] …. height[j-1] } in the monotone increasing queue can be the left side of the rectangle.
    • Before adding current height, i.e. height[j], to monotone increasing queue, for all the values in the queue that have height >= height[j] can be part of a rectangle of fixed height, height[j]. Thus, all such heights[i] are possible left sides of the current rectangle. Maximise the area of the rectangle possible in the histogram.
    • Pop all such heights from the queue and increase the breadth of the rectangle by 1. When there are no more elements to pop out of the queue. Push the current index in the queue, as it is guaranteed to follow monotone increasing height property.
  • Note that, if the histogram contains just one height, for such cases, initially push 0 to the queue to calculate maximum area.

 

The final algorithm will be-

  • At each row, we will maintain an additional 1- dimensional array height[] which denotes the height of contiguous 1’s at any column j, 0 <= j <= M-1, from bottom to top. Here bottom means current row i.
  • If the value of mat[i][j] = 0, then height[j] is set to 0, else it is incremented by 1.
  • This 1-dimensional height array at each row mimics the histogram. The only thing left is to apply the “Largest area in histogram” function to the updated height[] array in each row.
  • Maximise area at each step and return.
Time Complexity

O(N*M), where N denotes the number of rows of the matrix and M denotes the number of columns.

 

We will visit each cell of the binary matrix at most twice, hence the overall Time Complexity will be O(N*M).

Space Complexity

O(M), where M denotes the number of columns.

 

We are using one 1-dimensional array/list of size M, the overall Space Complexity will be O(M).

Code Solution
(100% EXP penalty)
Maximum size subrectangle
Full screen
Console