Workspace

Problem workspace

3 day streakD

Maximal Rectangle in a Binary Matrix

HardStacksAreas & contributions

The challenge

Return the largest area of an all-ones axis-aligned rectangle in a binary matrix.

Rectangular matrix of numeric 0 and 1; an empty matrix returns 0.

Example

[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] → 6.

Use the walkthrough below to inspect the input and each state change.

See Maximal Rectangle in a Binary Matrix, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Binary matrix · the current row builds histogram heights
Row 010100
Row 110111
Row 211111
Row 310010
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.Empty inputMain stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 39

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Accumulate column heights for each row; zero resets a height.

Indices are zero-based. C++ uses C++17 or later.

def histogram(heights):
    stack, best = [], 0
    for i in range(len(heights) + 1):
        height = heights[i] if i < len(heights) else 0
        while stack and heights[stack[-1]] > height:
            j = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, heights[j] * (i - left - 1))
        if i < len(heights): stack.append(i)
    return best


def solve(matrix):
    heights = [0] * (len(matrix[0]) if matrix else 0)
    best = 0
    for row in matrix:
        for c, value in enumerate(row):
            heights[c] = heights[c] + 1 if value else 0
        best = max(best, histogram(heights))
    return best

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap