85. Maximal Rectangle
Maximal Rectangle (LeetCode 85) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Largest Rectangle in Histogram subpattern.
How to solve Maximal Rectangle
Maximal Rectangle is a Largest Rectangle in Histogram problem, part of Stack Patterns. Learn the stack-based approach to find largest rectangle in histogram and maximal rectangle in matrix.
Work towards the solution in these steps:
- Consider how to transform the 2D matrix problem into multiple 1D problems that you can solve efficiently.
- Try to think of each row as a base and build a histogram of heights representing consecutive '1's above each cell.
- Recall how to find the largest rectangle in a histogram efficiently using a stack to track potential boundaries.
The reference solution runs in O(m * n) time and O(n) space.
The Maximal Rectangle solution and editorial walks through the full approach with reference code.
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'.
Topics and companies
Topics: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack.
Reported in interviews at Google, Amazon, Adobe, Bloomberg, Apple.
How to practise Maximal Rectangle on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(n) space.
Open Maximal Rectangle in the code editor, or read the Maximal Rectangle editorial for a worked solution with its approach and complexity analysis.
Where Maximal Rectangle sits in the DSA pattern sheet
Problems related to Maximal Rectangle
Other problems that use the same Largest Rectangle in Histogram and Stack Patterns techniques:
- Largest Rectangle in Histogram — Hard, same subpattern
- Asteroid Collision — Medium, same pattern
- Baseball Game — Easy, same pattern
- Basic Calculator — Hard, same pattern
- Basic Calculator II — Medium, same pattern
- Basic Calculator III — Hard, same pattern
Maximal Rectangle FAQ
What is the LeetCode number of Maximal Rectangle?
Maximal Rectangle is LeetCode problem 85, rated Hard.
What pattern is used to solve Maximal Rectangle?
Maximal Rectangle is a Largest Rectangle in Histogram problem. It belongs to the Stack Patterns pattern, in the Largest Rectangle in Histogram subpattern.
What is the time complexity of Maximal Rectangle?
The reference solution runs in O(m * n) time and O(n) space.
Which companies ask Maximal Rectangle?
Maximal Rectangle has been reported in interviews at Google, Amazon, Adobe, Bloomberg, Apple.