Scale Engineer

Maximal Rectangle

Hard
#0085Time: O(rows^2 * cols)Space: O(rows * cols)15 companies
Patterns
Dynamic Programming
Data structures
ArrayStackMatrixMonotonic Stack
Companies
AdobeAmazonAppleBloomberg

Prompt

Given a rows x cols 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 maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

 

Constraints:

  • rows == matrix.length
  • cols == matrix[i].length
  • 1 <= row, cols <= 200
  • matrix[i][j] is '0' or '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each cell (i, j) and considers it as the top-left corner of a potential maximal rectangle. For each such corner, it expands downwards row by row, calculating the maximum possible rectangle area. To optimize the width calculation, it precomputes the number of consecutive '1's to the right for every cell.

Algorithm

  • Initialize maxArea to 0.
  • If the matrix is empty, return 0.
  • Get the number of rows and columns.
  • Create a 2D integer array width of the same dimensions as the input matrix.
  • Precompute the width array. For each row i, iterate from right to left (from j = cols - 1 to 0):
    • If matrix[i][j] is '1', set width[i][j] to 1 + width[i][j+1]. If j is the last column, it's just 1.
    • If matrix[i][j] is '0', set width[i][j] to 0.
  • Iterate through each cell (i, j) of the matrix, considering it as a potential top-left corner of a rectangle.
  • For each (i, j):
    • Initialize minWidth to a very large value.
    • Iterate downwards from the current row k = i to the last row.
      • Update minWidth to be the minimum of its current value and width[k][j]. This minWidth represents the width of the rectangle that spans from row i to k starting at column j.
      • If minWidth becomes 0, it means the rectangle is broken, so we can break the inner loop.
      • Calculate the height of the current rectangle as k - i + 1.
      • Calculate the area as minWidth * height.
      • Update maxArea with the maximum area found so far.
  • Return maxArea.

Walkthrough

A brute-force solution would be to check every possible rectangle, which is highly inefficient. We can improve this by fixing the top-left corner and the height of the rectangle and then finding the maximum possible width.

This approach pre-calculates, for each cell (i, j), the number of consecutive '1's to its right, including itself. Let's call this width[i][j]. This precomputation step takes O(rows * cols) time.

After precomputation, the main algorithm iterates through every cell (i, j) as a potential top-left corner. For each (i, j), it iterates downwards to every possible bottom row k. For a rectangle defined by top-left (i, j) and bottom row k, the height is k - i + 1. The width is limited by the narrowest stretch of '1's starting from column j in any row from i to k. This is equivalent to min(width[i][j], width[i+1][j], ..., width[k][j]). We calculate this area and update our global maximum.

class Solution {    public int maximalRectangle(char[][] matrix) {        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {            return 0;        }        int rows = matrix.length;        int cols = matrix[0].length;        int[][] width = new int[rows][cols];         // Precompute width of consecutive '1's to the right        for (int i = 0; i < rows; i++) {            for (int j = cols - 1; j >= 0; j--) {                if (matrix[i][j] == '1') {                    width[i][j] = (j == cols - 1) ? 1 : width[i][j + 1] + 1;                } else {                    width[i][j] = 0;                }            }        }         int maxArea = 0;        // Iterate through each cell as a potential top-left corner        for (int i = 0; i < rows; i++) {            for (int j = 0; j < cols; j++) {                int minWidth = Integer.MAX_VALUE;                // Expand downwards                for (int k = i; k < rows; k++) {                    // The width of the rectangle is limited by the narrowest row                    minWidth = Math.min(minWidth, width[k][j]);                    if (minWidth == 0) break; // No more rectangle possible                    int height = k - i + 1;                    maxArea = Math.max(maxArea, minWidth * height);                }            }        }        return maxArea;    }}

Complexity

Time

O(rows^2 * cols)

Space

O(rows * cols)

Trade-offs

Pros

  • More intuitive and easier to come up with than the most optimal solution.

  • It's a significant improvement over a naive O(rows^3 * cols^3) brute-force approach.

Cons

  • The time complexity of O(rows^2 * cols) can be too slow for large matrices.

  • It uses extra space proportional to the size of the matrix, which can be significant.

Solutions

using System ; using System.Collections.Generic ; using System.Linq ; public class Solution { private int MaximalRectangleHistagram ( int [] height ) { var stack = new Stack < int >(); var result = 0 ; var i = 0 ; while ( i < height . Length || stack . Any ()) { if (! stack . Any () || ( i < height . Length && height [ stack . Peek ()] < height [ i ])) { stack . Push ( i ); ++ i ; } else { var previousIndex = stack . Pop (); var area = height [ previousIndex ] * ( stack . Any () ? ( i - stack . Peek () - 1 ) : i ); result = Math . Max ( result , area ); } } return result ; } public int MaximalRectangle ( char [][] matrix ) { var lenI = matrix . Length ; var lenJ = lenI == 0 ? 0 : matrix [ 0 ]. Length ; var height = new int [ lenJ ]; var result = 0 ; for ( var i = 0 ; i < lenI ; ++ i ) { for ( var j = 0 ; j < lenJ ; ++ j ) { if ( matrix [ i ][ j ] == '1' ) { ++ height [ j ]; } else { height [ j ] = 0 ; } } result = Math . Max ( result , MaximalRectangleHistagram ( height )); } return result ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem