We have a 2D grid of characters where each cell is either '1' or '0'. We need to find the largest axis-aligned rectangle that contains only '1's and return its area.

A brute force approach tries every possible rectangle defined by a top-left and bottom-right corner, then checks whether all cells inside are '1'. That is slow. The faster idea is to reduce this 2D problem to something solvable in linear time per row.

Reading the matrix row by row, we can build a histogram of heights. For each cell (r, c), the height is the number of consecutive '1's ending at row r in column c. Finding the largest rectangle in a single row's histogram is the "Largest Rectangle in Histogram" problem, solvable in O(cols) time using a stack. Solving it for every row and taking the maximum gives the answer.

Key Constraints:

Intuition

Try every possible rectangle in the matrix and check if it contains only '1's. A rectangle is defined by its top-left corner (r1, c1) and bottom-right corner (r2, c2). For each one, we verify that every cell inside is '1'.

Scanning every cell of every rectangle would add another factor of rows * cols, so we use a 2D prefix sum instead. With the prefix sum precomputed, checking whether a rectangle is all '1's is O(1): if the sum over the rectangle equals its area, every cell in it is 1.

Even with this optimization, we still enumerate all O(rows^2 * cols^2) possible rectangles, which is about 1.6 billion for a 200x200 matrix.

Algorithm

Example Walkthrough

Input:

We build the prefix sum first, then enumerate rectangles. Using 1-indexed prefix coordinates, the rectangle with (r1, c1) = (2, 3) and (r2, c2) = (3, 5) covers the original cells in rows 1-2, columns 2-4 (the block of six 1s in the bottom-right). Its prefix sum is prefix[3][5] - prefix[1][5] - prefix[3][2] + prefix[1][2] = 6, and its area is (3 - 2 + 1) * (5 - 3 + 1) = 2 * 3 = 6. Sum equals area, so every cell is 1, and maxArea becomes 6.

Other rectangles update maxArea along the way: the single cells give area 1, the full first column gives a 4 * 1 all-1 strip of area 4, and the 1 1 1 block in row 2 gives area 3. None of the all-1 rectangles exceeds 6. After the four nested loops finish, the answer is 6.

Code

Enumerating all rectangles is too slow for large matrices. The next approach treats each row as a histogram and finds the largest rectangle in that histogram in linear time.

Intuition

Process the matrix one row at a time, from top to bottom. For each column, track a height: the number of consecutive '1's ending at the current row. A '0' resets the height to 0, and a '1' makes the height one more than the height in that column at the row above.

Each row's heights form a histogram. The largest rectangle in a histogram is computable in O(cols) with a monotonic stack. Running that over every row's histogram and taking the maximum gives the answer.

For the matrix from Example 1, the per-row histograms are:

The monotonic stack finds the largest rectangle in a histogram by keeping bar indices in increasing height order. When a shorter bar appears, the taller bars on the stack can no longer extend further right, so we pop them and compute the area each one anchors.

Algorithm

The monotonic stack sub-routine iterates through indices 0 to cols (using a sentinel height of 0 at the end). When the current height is less than the top of the stack, we pop and compute area = height * width, where width extends from the current position back to the new stack top.

Example Walkthrough

Code

This approach is optimal at O(rows * cols), though it relies on the monotonic stack sub-routine. The next approach solves the problem with dynamic programming alone, trading some time for a stack-free implementation.

Intuition

This approach uses dynamic programming without a stack. For each cell (r, c) that contains '1', compute the width: the number of consecutive '1's ending at column c in row r, counting leftward. To find the largest rectangle whose bottom-right corner is (r, c), expand upward row by row. As the rectangle grows taller, its usable width can only shrink to the minimum width seen across the rows it spans, since every row in the rectangle must be at least that wide. At each row, the candidate area is min_width * height, and we keep the maximum.

For example, if cell (2, 4) has width 5 and cell (1, 4) has width 3, then a rectangle of height 2 anchored at (2, 4) has width min(5, 3) = 3, giving area 6.

Algorithm

Example Walkthrough

Code