How do you solve Maximal Rectangle on LeetCode?

Maximal Rectangle (LeetCode #85) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * m) time complexity and O(m) space complexity. Key insight: Transforming the problem into histograms allows for efficient area calculations.

What is the brute force solution for Maximal Rectangle?

The brute force approach for Maximal Rectangle is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible rectangle in the matrix to find the largest rectangle filled with 1's. This is straightforward but inefficient, as it examines all combinations. The optimal Optimal Solution approach improves this to O(n * m).

What algorithm or data structure is used to solve Maximal Rectangle?

Maximal Rectangle uses the following concepts: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack. The recommended patterns to study are: Histogram Area, Dynamic Programming.

What are the interview tips for Maximal Rectangle?

Understand how to break down the problem into manageable parts. Practice explaining your thought process clearly during the interview. Be prepared to discuss time and space complexity.

What are common mistakes when solving Maximal Rectangle?

Not resetting heights correctly when encountering '0'. Failing to handle edge cases like empty matrices.

#85

Maximal Rectangle

Hard

ArrayDynamic ProgrammingStackMatrixMonotonic StackHistogram AreaDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n * m)
Space	O(1)	O(m)

💡

Intuition

Time O(n * m)Space O(m)

The optimal solution transforms the problem into a series of histogram problems. By treating each row as the base of a histogram, we can efficiently calculate the largest rectangle using a stack.

⚙️

Algorithm

3 steps

1Step 1: Create an array to store heights of 1's for each column.
2Step 2: For each row in the matrix, update the heights array. If the cell is '1', increment the height; if it's '0', reset the height to 0.
3Step 3: For each updated heights array, calculate the maximum rectangle area using a stack to find the largest rectangle in the histogram.

solution.py22 lines

1def maximalRectangle(matrix):
2    if not matrix:
3        return 0
4    max_area = 0
5    heights = [0] * len(matrix[0])
6    for row in matrix:
7        for i in range(len(row)):
8            heights[i] = heights[i] + 1 if row[i] == '1' else 0
9        max_area = max(max_area, largestRectangleArea(heights))
10    return max_area
11
12def largestRectangleArea(heights):
13    heights.append(0)
14    stack = []
15    max_area = 0
16    for i in range(len(heights)):
17        while stack and heights[stack[-1]] > heights[i]:
18            h = heights[stack.pop()]
19            w = i if not stack else i - stack[-1] - 1
20            max_area = max(max_area, h * w)
21        stack.append(i)
22    return max_area

ℹ

Complexity note: The time complexity is O(n * m) because we iterate through each cell in the matrix once and then process the heights array, while the space complexity is O(m) for the heights array.

1Transforming the problem into histograms allows for efficient area calculations.
2Using a stack helps manage heights and widths effectively.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.