Abstract / Summary

Find the largest rectangle area in a histogram formed by consecutive columns in a binary matrix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Matrix
• Monotonic Stack
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation computes the area of the largest rectangle consisting solely of 1s in a binary matrix. It proceeds in three distinct phases: conversion of the input from strings to integers, construction of a horizontal prefix sum that records consecutive 1s in each row, and a double-nested scan that expands vertically while tracking the minimal width encountered. The result is the maximal product of width and height observed during the scan.

Conversion of Input Types

The first nested loops replace each character '0' or '1' with its numeric counterpart. By performing the conversion in place, the algorithm avoids allocating an auxiliary structure.

for y in range(height):
    for x in range(width):
        matrix[y][x] = int(matrix[y][x])

This step guarantees that subsequent arithmetic operations work directly on integer values, simplifying the logic for the prefix-sum phase.

Prefix Sum Construction

The second pair of loops builds a running count of consecutive 1s to the left of each cell. When a cell and its immediate left neighbor are both non-zero, the current cell accumulates the left neighbor’s count. The operation is also performed in place, reusing the original matrix storage.

for y in range(height):
    for x in range(1, width):
        if matrix[y][x] != 0 and matrix[y][x-1] != 0:
            matrix[y][x] += matrix[y][x-1]

After this phase, each entry holds the length of the longest horizontal stretch of 1s ending at that column for its row. This compact representation enables the later vertical scan to retrieve width information instantly without recomputing row-wise runs.

Main Scanning Loop

The core of the algorithm iterates column by column, then row by row, expanding a vertical window downward from each starting cell. Two variables, w (current minimal width) and h (current height), are updated as the scan proceeds. If a zero is encountered, the inner vertical scan terminates early, preventing unnecessary work.

result = 0
for x in range(width):
    for y in range(height):
        w = width
        h = 0
        for scan in range(y, height):
            if matrix[scan][x] == 0:
                break
            w  = min(w, matrix[scan][x])
            h += 1
            result = max(result, w*h)

The inner loop maintains w as the smallest horizontal run among the rows visited so far, ensuring that any rectangle considered is fully composed of 1s. Multiplying w by the current height h yields the area of the candidate rectangle, and result retains the largest area found.

Edge Cases Handled

When the matrix contains only zeros, the prefix-sum phase leaves all entries at zero, causing the vertical scan to break immediately at each starting cell; the final result remains zero, correctly indicating the absence of any rectangle of 1s.

A single-row matrix is processed without special treatment: the prefix sum records the lengths of consecutive 1s, and the vertical scan runs only one iteration, yielding the maximal horizontal stretch as the area.

Similarly, a single-column matrix bypasses the horizontal prefix accumulation (since the inner loop starts at index 1) and relies on the vertical scan to count consecutive 1s, producing the correct maximal vertical length.

The conversion step also tolerates matrices where each element is already an integer; the int() cast is idempotent, leaving the values unchanged.

Performance Optimizations

The algorithm reuses the input matrix for both type conversion and prefix-sum storage, eliminating the need for extra arrays and reducing memory pressure.

By updating the width w with min(w, matrix[scan][x]) during the vertical expansion, the code avoids recomputing the minimum across the visited rows after each step, achieving constant-time updates.

The early break when a zero is encountered in the vertical scan prevents the inner loop from traversing rows that cannot contribute to a valid rectangle, cutting off unnecessary iterations especially in sparse matrices.

Limiting the initial width w to the total number of columns (width) provides a safe upper bound that is quickly tightened as soon as the first row is examined, ensuring that the multiplication w*h never overestimates the feasible area.

Overall, the in-place transformations and early termination conditions combine to keep the execution tight and memory-efficient while still exploring all viable rectangle configurations.

Imagine you have a big sheet of graph paper filled with little squares. Some squares are colored black and some are left empty. The goal is to find the biggest rectangle you can draw using only the empty squares.

First, the computer looks at every single square on the paper. It turns the text labels into numbers so it can do math with them. It gives every empty square a value of one and every dark square a value of zero.

Next, it visits every row and counts how many empty squares are sitting side by side. If a row has three empty squares in a line, the computer updates those squares to say one, two, and three. This helps the computer remember how wide the empty space is at that exact spot.

Finally, the computer plays a game of looking for shapes. It picks a starting point and looks down through the rows. As it moves down, it checks how wide the empty space is, which it already calculated. It keeps going down as long as it finds empty squares, making the rectangle taller and taller while keeping track of its width. Every time it finds a new rectangle, it checks to see if it is bigger than the last one it found. It does this over and over until it has checked every possible rectangle on the entire sheet of paper.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java			TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python	C#	Rust		Java		Go	TS
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	everthis					JS
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan						Java
	halfrost								Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru				Rust
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	vli02							C
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
vli02	C
wisdompeak	C++
withaarzoo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality