How do you approach Maximal Rectangle?

Think of each row as the base of a histogram.

What is the time complexity of Maximal Rectangle?

Time complexity: O(m * n). Space complexity: O(n).

What are common mistakes on Maximal Rectangle?

Picking the wrong strictness. > and >= differ only on ties, and ties are where these problems keep their test cases. Not draining the stack after the loop, which drops every element that never found its boundary. Storing values when the answer is a distance, which needs indices.

Sitelet https://gitgood.dev/coding/maximal-rectangle

gitGood.dev

← Back to problems

Maximal Rectangle

HardAlgorithms

Description

Given a rows x cols binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.

Example 1

Input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

Output: 6

Explanation: The maximal rectangle is shown in rows 2-3, columns 2-4 with area 6.

Example 2

Input: matrix = [[0]]

Output: 0

Example 3

Input: matrix = [[1]]

Output: 1

Constraints

- rows == matrix.length - cols == matrix[i].length - 1 <= rows, cols <= 200 - matrix[i][j] is 0 or 1

Maximal Rectangle: approach, complexity and pitfalls

A hard monotonic stack problem, graded against 6 test cases (3 of them hidden).

The pattern: Monotonic Stack

A stack kept sorted, for next-greater and largest-rectangle style questions.

Reach for it when you see: "Next greater/smaller element", or a maximum rectangle/area over a histogram.

If you are stuck

Show the 3-step hint ladder

Think of each row as the base of a histogram.
Build up histogram heights row by row - reset to 0 when a cell is 0.
Apply the Largest Rectangle in Histogram algorithm for each row.

The optimal approach

Show the approach: Histogram per Row

Treat each row as the base of a histogram. For each row, compute the heights of consecutive 1s above (including the current row). Then apply the Largest Rectangle in Histogram algorithm on these heights to find the max rectangle ending at this row.

Time: O(m * n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Monotonic Stack mistakes

These apply to the pattern as a whole, not just this problem.

Picking the wrong strictness. `>` and `>=` differ only on ties, and ties are where these problems keep their test cases.
Not draining the stack after the loop, which drops every element that never found its boundary.
Storing values when the answer is a distance, which needs indices.