Maximal Rectangle - Video Solutions

Problem Overview: You are given a binary matrix filled with 0s and 1s. The task is to compute the area of the largest rectangle containing only 1s. The rectangle must be formed using adjacent cells in the grid.

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

Convert each matrix row into a histogram. Maintain an array heights where heights[j] represents the number of consecutive 1s above the current cell (including the current row). For every row, update this histogram and compute the largest rectangle in the histogram using a monotonic increasing stack. The stack keeps column indices where heights are increasing. When a shorter bar appears, pop from the stack and calculate area using the popped height as the limiting bar.

This technique reuses the classic "Largest Rectangle in Histogram" pattern. Each column index is pushed and popped at most once, so histogram processing runs in O(n) per row. Across m rows, the total runtime becomes O(m*n). The stack stores indices only, giving O(n) extra space. This method combines stack, monotonic stack, and array processing.

Approach 2: Dynamic Programming with Left/Right Boundaries (O(m*n) time, O(n) space)

Track three arrays while scanning each row: height, left, and right. height[j] stores consecutive vertical 1s like the histogram approach. left[j] records the leftmost boundary where a rectangle of height height[j] can extend, while right[j] tracks the right boundary. Update left by scanning left-to-right and update right by scanning right-to-left.

Once these arrays are updated for the current row, compute the area for every column using (right[j] - left[j]) * height[j]. This approach effectively performs dynamic programming across rows, carrying forward rectangle constraints. Each cell is processed a constant number of times, giving O(m*n) time and O(n) space. The technique relies heavily on dynamic programming and careful boundary tracking inside the matrix.

Recommended for interviews: The histogram + monotonic stack approach is the one most interviewers expect. It shows you can transform a 2D problem into repeated 1D histogram problems and apply a known stack pattern. The dynamic programming boundary method is also optimal and sometimes easier to reason about, but the histogram technique demonstrates stronger pattern recognition.