Maximum Rectangles
PhonePeThe problem
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.
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.
Input : matrix = [[1]] Output: 1 Explanation: In this case, there is only one rectangle with area 1.
Input: matrix = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1]]
- 1<=n,m<=1000
- 0<=matrix[i][j]<=1
cpp
class Solution
{
public:
int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &matrix){
}
};java
class Solution {
public int maximalAreaOfSubMatrixOfAll1(int[][] matrix) {
}
}python
class Solution:
def maximalAreaOfSubMatrixOfAll1(self, matrix):javascript
class Solution {
maximalAreaOfSubMatrixOfAll1(matrix) {
}
}csharp
public class Solution
{
public int MaximalAreaOfSubMatrixOfAll1(int[][] matrix){
}
}go
func maximalAreaOfSubMatrixOfAll1(matrix [][]int) int {
}Stuck? Show a way to structure it+
- 01Maintain one histogram height per column.
- 02Update heights row by row.
- 03Run largest-rectangle-in-histogram on each row.
- 04Keep the global maximum.
- 05Reset heights to zero where the matrix has zero.
Reference answer
Then expect these follow-ups
How would you return the coordinates of the best rectangle?
Tests: implementation extension
What changes if the matrix is streamed row by row?
Tests: constraint adaptation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question