Maximal Rectangle

Problem

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.

Bonus if you can solve it in O(n^2) or less.

Examples

Example 1:

$\begin{array}{|c|c|c|c|c|} \hline 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 \\ \hline 1 & 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 \\ \hline 1 & 0 & 0 & 1 & 0 \\ \hline \end{array}$

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.

Solution

This problem can be converted to Largest Rectangle in Histogram.

Method 1 - Brute Force

Here is the naive approach:

Iterate Over All Possible Submatrices:
- Use nested loops to treat each cell (i, j) as the top-left corner of a potential rectangle.
- For each top-left corner, use nested loops to treat each cell (p, q) as the bottom-right corner.
- Check if the submatrix from (i, j) to (p, q) contains only 1s using the isAllOnes method.
- If it does, calculate the area and update maxArea if the calculated area is larger.
Helper Method (isAllOnes): Check if all elements in the submatrix from (startX, startY) to (endX, endY) are 1.

Code

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '0') continue;

                for (int p = i; p < rows; p++) {
                    for (int q = j; q < cols; q++) {
                        if (matrix[p][q] == '0') continue;

                        if (isAllOnes(matrix, i, j, p, q)) {
                            int area = (p - i + 1) * (q - j + 1);
                            maxArea = Math.max(maxArea, area);
                        }
                    }
                }
            }
        }

        return maxArea;
    }

    private boolean isAllOnes(char[][] matrix, int startX, int startY, int endX, int endY) {
        for (int x = startX; x <= endX; x++) {
            for (int y = startY; y <= endY; y++) {
                if (matrix[x][y] == '0') {
                    return false;
                }
            }
        }
        return true;
    }
}

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows = len(matrix)
        cols = len(matrix[0])
        max_area = 0

        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '0':
                    continue

                for p in range(i, rows):
                    for q in range(j, cols):
                        if matrix[p][q] == '0':
                            continue

                        if self.is_all_ones(matrix, i, j, p, q):
                            area = (p - i + 1) * (q - j + 1)
                            max_area = max(max_area, area)

        return max_area

    def is_all_ones(self, matrix: List[List[str]], start_x: int, start_y: int, end_x: int, end_y: int) -> bool:
        for x in range(start_x, end_x + 1):
            for y in range(start_y, end_y + 1):
                if matrix[x][y] == '0':
                    return False
        return True

Complexity

⏰ Time complexity: O((rows * cols)^3) as we’re checking every possible sub-matrix.
🧺 Space complexity: O(1) as we only use a few additional variables.

Method 2 - Using Largest Rectangle in Histogram 🏆

We can use Largest Rectangle in Histogram here. So, our problem is:

Row-wise convert matrix to histogram
Then find the largest histogram.

So, this is how the approach will be:

Dynamic Programming Table: We use a heights array where heights[j] represents the number of consecutive 1s ending at column j for the current row i.
Histogram Algorithm: For each row treated as the base, compute the largest rectangle area in the histogram represented by heights using a stack-based approach.
Area Calculation: The maximum area found while iterating through rows is the answer.

Lets see how to convert the matrix in histogram.

Lets consider the matrix:

1  1  0  0  1  0
0  1  1  1  1  1
1  1  1  1  1  0
0  0  1  1  0  0

Convert first row to histogram, our heights for row[0]:

1
2

hist = 1  1  0  0  1  0
area = 2 (h = 1, l = 2)

First row is easy. For subsequent rows, whenver we see last row or base row having 0, we make our height 0, else we will sum up the pillar or column values.

Now, for row[2]:

1
2

hist = 0  2  1  1  2  1
area = 4 (h = 1, l = 4)

For row[3]:

1
2

1  3  2  2  3  0
area = 8 (h = 2, l = 4)

Finally row[4]:

1
2

0  0  3  3  0  0
area = 6 (h = 3, l = 2)

As, we can see row[3] histogram gave us our maximal area, that is the answer:

\begin{array}{|c|c|c|c|c|c|} \hline 1 & \colorbox{Red} 1 & 0 & 0 & \colorbox{Yellow}1 & 0 \\ \hline 0 & \colorbox{Red} 1 & \colorbox{YellowOrange} 1 & \colorbox{Green} 1 & \colorbox{Yellow} 1 & 1 \\ \hline \colorbox{Blue}1 & \colorbox{Red}1 & \colorbox{YellowOrange} 1 & \colorbox{Green} 1 & \colorbox{Yellow} 1 & 0 \\ \hline 0 & 0 & 1 & 1 & 0 & 0 \\ \hline \end{array} $$

Code

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
	        return 0;
	    }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] heights = new int[cols];
        int ans = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            ans = Math.max(ans, largestRectangleArea(heights));
        }
        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i <= len; i++) {
            int h = (i == len) ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        
        rows, cols = len(matrix), len(matrix[0])
        heights: List[int] = [0] * cols
        ans: int = 0

        for i in range(rows):
            for j in range(cols):
                heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
            ans = max(ans, self.largestRectangleArea(heights))
        
        return ans

    def largestRectangleArea(self, heights: List[int]) -> int:
        stack: List[int] = []
        max_area: int = 0
        len_heights: int = len(heights)
        
        for i in range(len_heights + 1):
            h = heights[i] if i < len_heights else 0
            while stack and h < heights[stack[-1]]:
                height: int = heights[stack.pop()]
                width: int = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        
        return max_area

Complexity

⏰ Time complexity: O(rows * cols) because we iterate through each element of the matrix once and compute the area for each row-constructed histogram in O(cols).
🧺 Space complexity: O(cols) for the heights array and the stack used in the histogram calculation.

Method 3 - Using DP

The dynamic programming (DP) solution processes the matrix row by row, starting from the first row. The maximal rectangle area at row i and column j can be calculated as [right(i,j) - left(i,j)] * height(i,j). The variables left, right, and height can be updated using information from both the current row and the previous row, making this a DP solution. The transition equations are:

left(i, j) = max(left(i-1, j), cur_left) where cur_left is derived from the current row.
right(i, j) = min(right(i-1, j), cur_right) where cur_right is derived from the current row.
height(i, j) = height(i-1, j) + 1 if matrix[i][j] == '1'.
height(i, j) = 0 if matrix[i][j] == '0'.

Intuition and Approach

We iterate over each row, updating the height, left, and right arrays:

height[i] records the number of consecutive 1s in column i.
left[i] records the leftmost index j where, for all indices k from j to i, the height is at least height[i].
right[i] records the rightmost index j where, for all indices k from i to j, the height is at least height[i].

1. Updating `height`

for (int j = 0; j < n; j++) {
    if (matrix[i][j] == '1') {
        height[j]++;
    } else {
        height[j] = 0;
    }
}

2. Updating `left`

(left boundary, scanning left to right):

int leftBoundary = 0;
for (int j = 0; j < n; j++) {
    if (matrix[i][j] == '1') {
        left[j] = Math.max(left[j], leftBoundary);
    } else {
        left[j] = 0;
        leftBoundary = j + 1;
    }
}

Updating `right`

(right boundary, scanning right to left):

int rightBoundary = n;
for (int j = n - 1; j >= 0; j--) {
    if (matrix[i][j] == '1') {
        right[j] = Math.min(right[j], rightBoundary);
    } else {
        right[j] = n;
        rightBoundary = j - 1;
    }
}

Code

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int maxArea = 0;

        int[] left = new int[n];
        int[] right = new int[n];
        int[] height = new int[n];

        Arrays.fill(right, n);

        for (int i = 0; i < m; i++) {
            int currentLeft = 0, currentRight = n;

            // Update heights
            for (int j = 0; j < n; j++) {
                height[j] = (matrix[i][j] == '1') ? height[j] + 1 : 0;
            }

            // Update left boundary
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = Math.max(left[j], currentLeft);
                } else {
                    left[j] = 0;
                    currentLeft = j + 1;
                }
            }

            // Update right boundary
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(right[j], currentRight);
                } else {
                    right[j] = n;
                    currentRight = j;
                }
            }

            // Update max area
            for (int j = 0; j < n; j++) {
                maxArea = Math.max(maxArea, (right[j] - left[j]) * height[j]);
            }
        }

        return maxArea;
    }
}

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        max_area = 0

        left = [0] * n
        right = [n] * n
        height = [0] * n

        for i in range(m):
            current_left, current_right = 0, n

            # Update heights
            for j in range(n):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0

            # Update left boundary
            for j in range(n):
                if matrix[i][j] == '1':
                    left[j] = max(left[j], current_left)
                else:
                    left[j] = 0
                    current_left = j + 1

            # Update right boundary
            for j in range(n - 1, -1, -1):
                if matrix[i][j] == '1':
                    right[j] = min(right[j], current_right)
                else:
                    right[j] = n
                    current_right = j

            # Update max area
            for j in range(n):
                max_area = max(max_area, (right[j] - left[j]) * height[j])

        return max_area

Problem#

Examples#

Similar Problem#

Solution#

Method 1 - Brute Force#

Code#

Complexity#

Method 2 - Using Largest Rectangle in Histogram 🏆#

Code#

Complexity#

Method 3 - Using DP#

Intuition and Approach#

1. Updating height#

2. Updating left#

Updating right#

Code#

Problem

Examples

Similar Problem

Solution

Method 1 - Brute Force

Code

Complexity

Method 2 - Using Largest Rectangle in Histogram 🏆

Code

Complexity

Method 3 - Using DP

Intuition and Approach

1. Updating `height`

2. Updating `left`

Updating `right`

Code