Skip to main content
Talentd

Maximal Rectangle - Solution & Explanation

HardArrayDynamic ProgrammingStackMatrix20 min readAsked at: Amazon, Microsoft, Goldman Sachs +12
Practice this problem

Problem Statement

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's 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 the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

 

Constraints:

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

Approach Overview

Problem Overview: You are given a binary matrix filled with 0s and 1s. The task is to compute the area of the largest rectangle containing only 1s. The rectangle must be formed using adjacent cells in the grid.

Approach 1: Histograms + Monotonic Stack (O(m*n) time, O(n) space)

Convert each matrix row into a histogram. Maintain an array heights where heights[j] represents the number of consecutive 1s above the current cell (including the current row). For every row, update this histogram and compute the largest rectangle in the histogram using a monotonic increasing stack. The stack keeps column indices where heights are increasing. When a shorter bar appears, pop from the stack and calculate area using the popped height as the limiting bar.

This technique reuses the classic "Largest Rectangle in Histogram" pattern. Each column index is pushed and popped at most once, so histogram processing runs in O(n) per row. Across m rows, the total runtime becomes O(m*n). The stack stores indices only, giving O(n) extra space. This method combines stack, monotonic stack, and array processing.

Approach 2: Dynamic Programming with Left/Right Boundaries (O(m*n) time, O(n) space)

Track three arrays while scanning each row: height, left, and right. height[j] stores consecutive vertical 1s like the histogram approach. left[j] records the leftmost boundary where a rectangle of height height[j] can extend, while right[j] tracks the right boundary. Update left by scanning left-to-right and update right by scanning right-to-left.

Once these arrays are updated for the current row, compute the area for every column using (right[j] - left[j]) * height[j]. This approach effectively performs dynamic programming across rows, carrying forward rectangle constraints. Each cell is processed a constant number of times, giving O(m*n) time and O(n) space. The technique relies heavily on dynamic programming and careful boundary tracking inside the matrix.

Recommended for interviews: The histogram + monotonic stack approach is the one most interviewers expect. It shows you can transform a 2D problem into repeated 1D histogram problems and apply a known stack pattern. The dynamic programming boundary method is also optimal and sometimes easier to reason about, but the histogram technique demonstrates stronger pattern recognition.

Approach 1: Approach Using Histograms and Stack

This approach is inspired by transforming the binary matrix row by row into histograms. For each row, consider it as the base and calculate the height of '1's found upwards in each column (until a '0' is encountered, resetting the height). Using these heights, treat each row as a histogram problem where you need to find the largest rectangular area. You can apply the 'Largest Rectangle in Histogram' algorithm using a stack for efficient processing.

The approach uses a stack-based method to calculate the largest rectangle in every row's histogram representation. Each row computes its respective histogram heights, and a monotonically increasing stack is used to calculate the maximum possible area efficiently.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(n * m) where n is the number of rows and m is the number of columns.
Space Complexity: O(m), used by the 'heights' array and stack.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach involves using dynamic programming (DP) to compute not only the heights but also left and right boundaries for each row's histogram. By maintaining arrays for each row, you can determine the maximum potential width of a rectangle starting from each point and thereby compute the largest rectangle area efficiently.

In this C++ solution, three vectors are maintained for each row: height, left, and right. These vectors help in calculating the maximal rectangle that can be formed by treating each row as a histogram. Dynamic programming ensures that for each iteration all possible rectangle areas are computed while respecting prior computed values.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n * m) because each cell is processed in constant time.
Space Complexity: O(m), due to extra arrays for heights, and boundaries.

Try this approach in the editor →

Approach 3: Monotonic Stack

We can treat each row as the base of a histogram and calculate the maximum area of the histogram for each row.

Specifically, we maintain an array heights with the same length as the number of columns in the matrix, where heights[j] represents the height of the column at the j-th position with the current row as the base. For each row, we iterate through each column:

  • If the current element is '1', increment heights[j] by 1.
  • If the current element is '0', set heights[j] to 0.

Then, we use the monotonic stack algorithm to calculate the maximum rectangle area of the current histogram and update the answer.

The specific steps of the monotonic stack are as follows:

  1. Initialize an empty stack stk to store the indices of the columns.
  2. Initialize two arrays left and right, representing the index of the first column to the left and right of each column that is shorter than the current column.
  3. Iterate through the heights array heights, first calculating the index of the first column to the left of each column that is shorter than the current column, and store it in left.
  4. Then iterate through the heights array heights in reverse order, calculating the index of the first column to the right of each column that is shorter than the current column, and store it in right.
  5. Finally, calculate the maximum rectangle area for each column and update the answer.

The time complexity is O(m times n), where m is the number of rows in matrix and n is the number of columns in matrix.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach Using Histograms and Stack

Time Complexity: O(n * m) where n is the number of rows and m is the number of columns.
Space Complexity: O(m), used by the 'heights' array and stack.

Dynamic Programming Approach

Time Complexity: O(n * m) because each cell is processed in constant time.
Space Complexity: O(m), due to extra arrays for heights, and boundaries.

Monotonic Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Histograms + Monotonic StackO(m*n)O(n)Best general solution. Common interview pattern based on Largest Rectangle in Histogram.
Dynamic Programming with BoundariesO(m*n)O(n)Good when you prefer explicit DP state tracking instead of stack operations.

Video Solution

L13. Maximal Rectangle | Stack and Queue Playlist • take U forward • 134,342 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximal Rectangle easy or hard?
Maximal Rectangle is classified as a hard problem because it requires recognizing the reduction to the Largest Rectangle in Histogram problem. The combination of matrix processing and monotonic stack logic makes it challenging for many candidates.
How to solve Maximal Rectangle in O(m*n)?
Maintain a histogram of column heights while iterating row by row. For every row, treat the heights as a histogram and compute the largest rectangle using a monotonic increasing stack. Each column index is pushed and popped once, giving O(n) work per row and O(m*n) total complexity.
What is the best approach for Maximal Rectangle?
The most widely used approach converts each matrix row into a histogram and computes the largest rectangle using a monotonic stack. Each row updates column heights and reuses the "Largest Rectangle in Histogram" algorithm. This achieves O(m*n) time and O(n) space, which is optimal for this problem.
What data structure is used in Maximal Rectangle?
The optimal solution uses a monotonic stack along with arrays that track histogram heights. Some implementations also use dynamic programming arrays for left and right boundaries. Core topics include stacks, arrays, and matrix traversal.
What is the time complexity of Maximal Rectangle?
The optimal algorithms run in O(m*n) time where m is the number of rows and n is the number of columns. Each cell contributes to histogram updates once per row, and stack operations are amortized O(n) per row. Space complexity is typically O(n).
Maximal Rectangle Python or Java solution approach?
In Python or Java, the typical solution iterates through each matrix row, updates a height array, and calls a helper function that computes the largest histogram rectangle using a stack. The logic is identical across languages and runs in O(m*n) time.
Is Maximal Rectangle asked at Google, Amazon, or Meta?
Maximal Rectangle is considered a classic hard matrix problem and has appeared in interviews at companies like Amazon, Google, and Meta. It tests the ability to reduce a 2D problem to a 1D histogram problem and apply stack-based optimization.

Ready to solve this problem?

Practice Maximal Rectangle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Sorted Submatrices With Maximum Element at Most K

Next

Largest Rectangle in Histogram