Leetcode 85: Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Problem Analysis:

If iterating all possible rectangles, it’s the O(m²n²) time complexity(m is matrix’s row, n is matrix’s column).

Les’s try to use some solution that has better time complexity.

Suppose X(i, j) is the position in matrix row i and column j, left(i, j) is length of consecutive 1 values left of the X(i, j), right(i, j) is length of consecutive 1 values right of the X(i, j), height(i, j) is the length of consecutive 1 values up of the X(i, j), we can compute the rectangle area(i, j) = (right(i, j) — left(i, j)) * height(i, j).

Iterating from the first row to last row, we update the left(i, j) and right(i, j) to make the area (from left to right, and height(i, j)), all has the 1 values.

Finally, we get the max area.

We can optimize the space to store only one row values of left, right, height datas.

Solution:

unoptimized:

class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    if (cols == 0) return 0;
 
    int res = 0;
    vector<vector<vector<vector<bool>>>> dp(rows, vector<vector<vector<bool>>>(cols, vector<vector<bool>>(rows, vector<bool>(cols, false))));
    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        if (matrix[i][j] == '0') continue;
        for (int end_i = i; end_i < rows; ++end_i) {
          if (matrix[end_i][j] == '0') break;
          for (int end_j = j; end_j < cols; ++end_j) {
            if (matrix[end_i][end_j] == '0') break;
            if (end_i > i && !dp[i][j][end_i - 1][end_j]) break;
            if (end_j > j && !dp[i][j][end_i][end_j - 1]) break;
            dp[i][j][end_i][end_j] = true;
            res = max(res, (end_i - i + 1) * (end_j - j + 1));
          }
        }
      }
    }
  
    return res;
  }
};

optimized:

class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    if (cols == 0) return 0;
    vector<int> left(cols, 0);
    vector<int> right(cols, cols);
    vector<int> height(cols, 0);
    int area = 0;
    for (int i = 0; i < rows; ++i) {
      int current_left = 0;
      int current_right = cols;
      for (int j = 0; j < cols; ++j) {
        if (matrix[i][j] == '1') {
          ++height[j];
          left[j] = max(left[j], current_left);
        } else {
          height[j] = 0;
          left[j] = 0;
          current_left = j + 1;
        }
      }
   
      for (int j = cols - 1; j >=0; --j) {
        if (matrix[i][j] == '1') {
          right[j] = min(right[j], current_right);
        } else {
          right[j] = cols;
          current_right = j;
        }
      }
      for (int j = 0; j < cols; ++j) 
        area = max(area, (right[j] - left[j]) * height[j]);
    }
    return area;
  }
};

Time Complexity: O(mn)

Space Complexity: O(n)