Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Any all-ones rectangle has a bottom row. At that row, let each column's height count consecutive ones ending there. The rectangle becomes a span of histogram bars whose minimum height determines its area. Solving the histogram problem for every possible bottom row therefore covers every matrix rectangle.

Approach

Maintain column heights, incrementing a height for 1 and resetting it for 0. Reserve one extra zero-height column as a sentinel.
For each row, scan its histogram with a stack of indices whose heights are strictly increasing.
Before pushing a column, pop every stacked bar at least as tall as it. For a popped height, the current column closes its usable span on the right; the remaining stack top identifies the last shorter bar on the left. Its width is current - leftBoundary - 1, using -1 when the stack is empty.
Update the best area for each popped bar. Equal heights are merged implicitly: the later equal bar can eventually represent the wider span.
The sentinel flushes the stack at the end of each row. Return the best area across all rows.

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        height = [0] * (m + 1)
        res = 0

        for i in range(n):
            for j in range(m):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0

            s = [0]
            for j in range(1, m + 1):
                while s and height[s[-1]] >= height[j]:
                    h = height[s.pop()]
                    w = j - 1 - (s[-1] if s else -1)
                    res = max(res, h * w)
                s.append(j)

        return res

Complexity analysis

For R rows and C columns, each matrix cell is processed once and each histogram index is pushed and popped at most once per row. Time is O(RC) and auxiliary space is O(C) for the heights and monotonic stack.