Maximal Rectangle

Maximal rectangle finds the largest rectangle of 1s in a binary matrix. Considering every possible rectangle is far too slow, and the efficient solution comes from recognising a problem already solved. Process the matrix row by row, and at each row ask what the largest rectangle ending at that row is. If, for each column, the count of consecutive 1s reaching upward is known, that row of counts is a histogram: - Each row becomes a histogram of column heights, and the answer is the largest rectangle in that histogram — reducing this Hard problem to Largest Rectangle in Histogram. The heights update incrementally. For each cell, a 1 increments the height carried from the row above, and a 0 resets it to zero. That reset is essential — a zero breaks the column, so no rectangle can span it. Then run the histogram routine on each row and keep the largest result across all rows. The histogram subroutine uses a monotonic increasing stack. Bars are pushed while heights increase; when a shorter bar arrives, taller bars are popped and each popped bar's rectangle is measured — its width running from the previous stacked index to the current one. Appending a sentinel height of 0 after the last bar flushes the stack, ensuring every remaining bar is measured. Without it, bars left on the stack are never evaluated and the answer comes out short on rows that end tall. The total cost is O(rows × cols): each row's histogram is built in O(cols) and processed in O(cols), since every bar is pushed and popped at most once.

Each row becomes a histogram: the height at a column is how many consecutive 1s sit above it. Then Largest Rectangle in Histogram runs once per row. Reducing a 2-D problem to a known 1-D one, row by row, is the transferable move.