2Brute2Best
🔥0

Maximal Rectangle

Hard·LeetCode #85 Pro OnlyPattern Transfer
LeetCode
01

Problem Statement

You are given a grid matrix of rows × cols cells. Each cell holds the character '0' or '1'.

Find the biggest rectangle (with sides along the grid lines) that contains only '1' cells, and return its area.

Input

A 2D grid matrix of characters, each '0' or '1'.

Output

One integer: the area of the largest all-'1' rectangle.

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

Rows 1–2, columns 2–4 are all '1': a 2 × 3 rectangle with area 6.

Example 2
Input: matrix = [["0"]]
Output: 0
Example 3
Input: matrix = [["1"]]
Output: 1
Constraints
  • • 1 ≤ rows, cols ≤ 200
  • • matrix[i][j] is '0' or '1'
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“largest rectangle”
→ Same goal as the histogram problem, but in 2D.
“containing only '1's”
→ Fix the bottom row; each column becomes a bar = the run of '1's going up.
“up to 200 × 200”
→ O(R · C) with a per-row histogram is clean; O(R² · C²) over all rectangles is not.
03

Approach Complexity Ladder

Brute Force — every cell as the bottom-right cornerO(R² · C)O(R · C)

For each cell, grow the rectangle upwards keeping the narrowest row width

Optimal — a histogram per row + monotonic stackO(R · C)O(C)

Build column heights row by row and run Largest Rectangle in Histogram on each row

Brute Force Intuition

First count, for each cell, how many '1's in a row end there going left (width[r][c]). Then treat each cell as the bottom-right corner of a rectangle and walk upwards. The rectangle can only be as wide as its narrowest row, so keep a running minimum of width and check minWidth × height at each step.

Recognition rule for this sub-pattern:

For each element, find how far it stretches left and right as the min (or max). Histograms: area = height × width. Sums over subarrays: value × (left span) × (right span), with one side strict and the other ≤ so ties count once.
Remember this · Monotonic Stack
Trigger
Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"
Think
When a new element arrives, which older elements can never be the answer again?
Key question
Is my stack increasing or decreasing, and what do I record when I pop?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track
C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track
Sum of Subarray RangesTrapping Rain Water (stack approach)