Skip to content

0085. Maximal Rectangle

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:

img

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 = []
Output: 0

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

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

Analysis

height[i] record the current number of countinous '1' in column i; left[i] record the left most index j which satisfies that for any index k from j to i, height[k] >= height[i], right[i] record the right most index j which satifies that for any index k from i to j, height[k] >= height[i] if j doesn't exist, then use size of matrix to represent j for right, use 0 to represent j for left.

matrix
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0

height
0 0 0 1 0 0 0
0 0 1 2 1 0 0
0 1 2 3 2 1 0

left
0 0 0 3 0 0 0
0 0 2 3 2 0 0
0 1 2 3 2 1 0

right
7 7 7 4 7 7 7 // at index i from right to left, if height[i] >= height[i+1], set right[i]=i or keep going
7 7 5 4 5 7 7
7 6 5 4 5 4 7

result
0 0 0 1 0 0 0
0 0 3 2 3 0 0
0 5 6 3 6 5 0

Code

class Solution {
public:
  int maximalRectangle(vector<vector<char>> &matrix) {
    if (matrix.empty())
      return 0;
    const int m = matrix.size();
    const int n = matrix[0].size();
    int left[n], right[n], height[n];
    fill_n(left, n, 0);
    fill_n(right, n, n);
    fill_n(height, n, 0);
    int maxA = 0;
    for (int i = 0; i < m; i++) {
      int cur_left = 0, cur_right = n;
      for (int j = 0; j < n;
           j++) { // compute height (can do this from either side)
        if (matrix[i][j] == '1')
          height[j]++;
        else
          height[j] = 0;
      }
      for (int j = 0; j < n; j++) { // compute left (from left to right)
        if (matrix[i][j] == '1')
          left[j] = max(left[j], cur_left);
        else {
          left[j] = 0;
          cur_left = j + 1;
        }
      }
      // compute right (from right to left)
      for (int j = n - 1; j >= 0; j--) {
        if (matrix[i][j] == '1')
          right[j] = min(right[j], cur_right);
        else {
          right[j] = n;
          cur_right = j;
        }
      }
      // compute the area of rectangle (can do this from either side)
      for (int j = 0; j < n; j++)
        maxA = max(maxA, (right[j] - left[j]) * height[j]);
    }
    return maxA;
  }
Last update: April 1, 2022