Maximal Rectangle

Problem Description

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.

Key Insights

• The problem can be visualized as finding the largest rectangle in a histogram, where each row of the matrix represents the base of the histogram.
• For each row, we can compute the height of 1s above the current row, treating it as a histogram.
• We can utilize a stack-based approach to efficiently calculate the maximal rectangle area for each histogram representation.

Space and Time Complexity

Time Complexity: O(rows * cols), as we need to traverse each cell of the matrix once. Space Complexity: O(cols), for the height array and the stack used in the histogram calculation.

Solution

We can solve the problem using a combination of dynamic programming and a monotonic stack. The approach involves the following steps:

1. Create an array heights that keeps track of the height of 1s for each column as we iterate through each row of the matrix.
2. For each row, update the heights array; if the cell contains 1, increment the height; if it contains 0, reset the height to 0.
3. For each updated heights array, calculate the maximal rectangle area using a monotonic stack. This involves finding the width of the rectangle for each height and calculating the area.
4. Keep track of the maximum area encountered during the iterations.

Code Solutions