Coding

Maximum Rectangles

Asked at

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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){
       
    }
}

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

Treat each matrix row as the base of a histogram. Maintain heights[c], the number of consecutive ones ending at the current row in column c. For a one, increment its height; for a zero, reset it to zero. After updating a row, solve largest rectangle in that histogram with an increasing stack and update the global best. Any all-one rectangle has a bottom row, so it will be considered when processing that row, and the histogram height captures its maximum possible upward extension. With R rows and C columns, each histogram pass is O(C), giving O(R times C) time overall. Heights and the stack use O(C) extra space. Avoid enumerating every rectangle or rerunning BFS; the key is reducing a two-dimensional condition to a one-dimensional monotonic-stack problem per row.

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

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question