# 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

# Solution

Approach 1: O(N^3): record the consecutive num of 1s for each row, and for each element go up to find the highest rectangle.

Approach 2: O(N^2): for each 1 in the matrix, record the max height above it (height of rectangle), and the left and right boundary where this max height extends to (width of rectangle).

Approach 3: O(N^2): Stack.

# Code (Python)

Approach 1:

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        # O(N^3): record the consecutive num of 1s for each row, and for each element go up to find the highest rectangle
        # S2 of https://leetcode.com/problems/maximal-rectangle/discuss/225690/Java-solution-with-explanations-in-Chinese
        num_ones = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        max_area = 0
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if c == 0:
                    num_ones[r][c] = 1 if matrix[r][c] == '1' else 0
                else:
                    num_ones[r][c] = num_ones[r][c-1] + 1 if matrix[r][c] == '1' else 0
                if num_ones[r][c] != 0:
                    width = num_ones[r][c]
                    for h in range(r, -1, -1): # need to account for every height above to avoid missing wide rectangles with high peaks
                        if num_ones[h][c] == 0:
                            break
                        width = min(width, num_ones[h][c])
                        max_area = max(max_area, width * (r - h + 1))
        return max_area

Approach 2:

    def maximalRectangle(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        
        # O(N^2): https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution
        # for each 1 in the matrix, record --
        # the max height above it (height of rectangle), and 
        # the left and right boundary where this max height extends to (width of rectangle)
        height, left, right = [0] * len(matrix[0]), [0] * len(matrix[0]), [len(matrix[0]) - 1] * len(matrix[0])
        max_area = 0
        for r in range(len(matrix)):
            left_bound = 0
            for c in range(len(matrix[0])):
                if matrix[r][c] == '1':
                    height[c] = height[c] + 1
                    left[c] = max(left[c], left_bound)
                else:
                    left_bound = c + 1
                    left[c] = 0
                    height[c] = 0
            right_bound = len(matrix[0]) - 1
            for c in range(len(matrix[0]) - 1, -1, -1):
                if matrix[r][c] == '1':
                    right[c] = min(right[c], right_bound)
                else:
                    right[c] = len(matrix[0])
                    right_bound = c - 1
                
                max_area = max(max_area, (right[c] - left[c] + 1) * height[c])

        return max_area

# Code (C++)

Approach 1:

Approach 2:

Approach 3:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        if (n == 0) return 0;
        int maxRect = 0;
        vector<int> height(n, 0);
        for (int i = 0; i < m; ++i)
        {
            stack<int> st;
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == '0')
                    height[j] = 0;
                else
                    height[j]++;
            }
            for (int j = 0; j <= n; ++j)
            {
                while (!st.empty() && (j == n || height[st.top()] > height[j]))
                {
                    int k = st.top();
                    st.pop();
                    int length = (!st.empty()) ? (j - st.top() - 1) : (j - 0);
                    maxRect = std::max(maxRect, length * height[k]);
                }
                st.push(j);
            }
        }
        return maxRect;
    }
};