Maximal Rectangle

Maximal Rectangle 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.

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), where m is the number of rows and n is the number of columns. For each row, we process all columns and compute the largest rectangle in a histogram in O(n) time. time and O(n), where n is the number of columns. We use O(n) space for the heights array and the stack used in the histogram calculation. 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

• Stack Patterns pattern guide
• Largest Rectangle in Histogram subpattern
• The full DSA patterns sheet
• All coding practice problems

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
• Basic Calculator — Hard, same pattern
• Basic Calculator II — Medium, same pattern
• Basic Calculator III — Hard, same pattern
• Daily Temperatures — Medium, same pattern