Largest Area Histogram Matrix

Compute the largest rectangle area in a binary matrix where each 1 forms part of a histogram.

stack histogram matrix maximal-rectangle

Write a function `largest_rectangle_area(matrix)` that takes a list of lists of integers (each element is 0 or 1) representing a binary matrix. The function should return the area of the largest rectangle that contains only 1's. The rectangle sides must be parallel to the matrix axes.

Input: `matrix` is a list of lists, possibly empty. The number of rows and columns can be up to 200 each, so an O(n*m) or O(n*m log m) algorithm is expected.

Output: an integer representing the maximum area.

Examples: see example_code.

Constraints:
- 0 <= number of rows <= 200
- 0 <= number of columns <= 200
- Each cell is 0 or 1.

Constraints

0 <= rows, cols <= 200. Each entry is 0 or 1. Time complexity O(rows*cols) expected.

Example

>>> largest_rectangle_area([[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]])
6
>>> largest_rectangle_area([])
0
>>> largest_rectangle_area([[0,0],[0,0]])
0
>>> largest_rectangle_area([[1]])
1

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of each row as the base of a histogram where the height is the consecutive 1's above it.

Use the classic largest rectangle in histogram algorithm for each row.

Maintain an array of heights, update it with each row.

Use a stack to compute the max area for each row in O(cols).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.