Maximal Rectangle - Solution & Explanation

Problem Overview: Maximal Rectangle asks you to find the largest rectangle containing only 1s in a binary matrix. The rectangle must be formed by contiguous cells. The challenge is efficiently evaluating all possible rectangles without checking every submatrix.

Approach 1: Histograms and Monotonic Stack (O(m*n) time, O(n) space)

The key insight is that every row can be treated as the base of a histogram. As you iterate through the matrix row by row, maintain a heights array where heights[j] counts consecutive 1s ending at the current row for column j. Each row converts the matrix into a histogram problem. You then compute the largest rectangle in that histogram using a stack, specifically a monotonic stack that keeps increasing bar heights.

The stack stores column indices. When the current height becomes smaller than the height at the stack top, you pop indices and compute rectangle areas where the popped bar becomes the limiting height. The width is determined using the next smaller element to the left and right. This avoids recomputing areas for every possible width. Since each column index is pushed and popped once per row, the overall complexity becomes O(m*n) time with O(n) extra space.

Approach 2: Dynamic Programming Boundaries (O(m*n) time, O(n) space)

This method maintains three arrays for each row: height, left, and right. The height array tracks consecutive vertical 1s just like the histogram approach. The left array stores the leftmost boundary where the rectangle can extend, while right stores the right boundary.

During each row scan, update height by incrementing for 1s and resetting for 0s. Then sweep from left to right to update the left boundary and from right to left to update right. The area at column j becomes (right[j] - left[j]) * height[j]. Tracking these boundaries effectively builds valid rectangles without explicitly using a stack. The approach relies heavily on dynamic programming and works in O(m*n) time with O(n) space.

Recommended for interviews: The histogram + monotonic stack approach is the one most interviewers expect. It shows that you can reduce a 2D rectangle problem into a sequence of 1D histogram problems and apply a classic stack pattern. Mentioning the brute-force rectangle enumeration demonstrates understanding of the problem space, but implementing the histogram stack solution proves strong algorithmic skills with arrays, stacks, and matrix transformations.