312. Maximum Rectangles

Given a m x n binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]

Output: 6

Explanation: The highlighted part depicts the rectangle with the largest area i.e. 6.

Example 2:

Input : matrix = [[1]] 

Output: 1 

Explanation: In this case, there is only one rectangle with area 1.

Now Your Turn!

Pick the correct output for the given input

Input: matrix = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1]]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  •   1<=n,m<=1000
  •   0<=matrix[i][j]<=1

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
class Solution
{
public:
int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &matrix){
}
};
Test Case

Input:

Matrix
to save your code