41. Maximum Size Rectangle of 1s in a Binary Matrix

Given a binary matrix, find the area of the largest rectangle made entirely of 1s. Print that area.

Input: The first line contains r and c, the matrix dimensions, space-separated. The next r lines each contain c space-separated binary values (0 or 1). Output: Print a single integer - the area of the largest all-1s rectangle in the matrix.

1 <= r, c <= 200

This problem builds directly on 'largest rectangle in a histogram' as a sub-routine - mastering that simpler 1D problem first makes this 2D version feel like a natural, incremental extension rather than an entirely new challenge.

Find the biggest rectangle made entirely of 1s hiding somewhere inside a grid of 0s and 1s. Brute force: Check every possible rectangle directly (every pair of top-left and bottom-right corners) and verify it's entirely made of 1s - this costs O(r² * c² ) or worse, far too slow for larger matrices. Optimised: Reducing the 2D problem to a SEQUENCE of 1D 'largest rectangle in a histogram' problems (one per row, building on the row above) turns an expensive 2D search into r independent, efficient O(c) stack-based computations - the histogram row by row captures exactly the vertical 'run of 1s' information needed to find rectangles spanning multiple rows.

Try every possible rectangle by choosing a top-left and bottom-right corner, and for each candidate rectangle scan all the cells inside to verify they are all 1s, tracking the maximum area among valid rectangles. This checks every possible rectangle directly and is correct, but the combination of choosing corners and verifying each rectangle's interior makes it extremely expensive. Time: O(r^3 * c^3) Space: O(1)

For each row, build a histogram of heights where height[i][j] is the number of consecutive 1s ending at row i in column j (0 if the cell itself is 0, otherwise 1 + the height above it). For each row's histogram, find the largest rectangle by, for every bar, scanning left and right while the height stays at least as tall as that bar, computing the enclosed area, and tracking the maximum. This reduces the 2D rectangle search to a per-row 1D histogram problem, a real complexity improvement over checking arbitrary rectangles directly. Time: O(r * c^2) Space: O(r * c)

Build the same row-wise histogram of consecutive-1 heights, but for each row, find the largest rectangle in that histogram using a monotonic increasing stack of bar indices: push bars while heights increase, and whenever a shorter bar is encountered, pop taller bars and compute the area they could span (using the current index and the new stack top as boundaries). This finds the largest histogram rectangle per row in linear time instead of quadratic, so the whole matrix is processed in time proportional to its size. Time: O(r * c) Space: O(r * c)

1. For each row, build a 'height histogram': for every column, how many consecutive 1s are stacked directly above (and including) this row in that column. 2. For each row's histogram, find the largest rectangle achievable using the classic 'largest rectangle in a histogram' technique (using a stack to efficiently find, for each bar, how far it can extend left and right before hitting a shorter bar). 3. Track the overall best rectangle area found across every row's histogram.

Time: O(r * c) - building each row's histogram is O(c), and the largest-rectangle-in-histogram algorithm itself is O(c) per row using a stack, giving O(r * c) total across all rows. Space: O(c), for the histogram array and the stack used in each row's rectangle computation.

r = 1 or c = 1 (degenerates to the longest run of 1s); a matrix of all 0s (answer 0); and r = c = 200 (largest, confirming the per-row histogram + stack approach is efficient).

Be ready to explain the histogram-building step clearly (each column's height either increases by 1 if the current cell is a 1, or resets to 0 if it's a 0) - this reduction to a known sub-problem is the entire key insight, and the histogram stack technique itself is worth mastering independently.