Finding the largest shape in a sea of data is a classic challenge that tests your ability to combine different algorithmic techniques. In this guide, we will explore how to transform a 2D matrix problem into a series of 1D histogram problems to find the maximum area efficiently.
Problem Summary
You're given:
- A 2D binary
matrixfilled with characters '0' and '1'.
Your goal:
- Find the largest rectangle containing only '1's and return its total area.
Example:
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.
Intuition
At first glance, checking every possible rectangle in a grid seems overwhelming. However, there is a clever trick: we can treat each row of the matrix as the "ground" and calculate the height of '1's stacked above it. By doing this, each row becomes a Histogram.
If we know how to find the largest rectangle in a histogram, we can simply repeat that process for every row in the matrix. To do this efficiently, we use a Monotonic Stack. For every bar in our histogram, we need to know:
- NSE (Next Smaller Element): The first bar to the right that is shorter than the current bar.
- PSE (Previous Smaller Element): The first bar to the left that is shorter than the current bar.
The width of the rectangle for any bar is . Multiplying this width by the bar's height gives us a potential area. We keep track of the maximum area found across all rows.
Code Blocks
C++ Solution
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<int> heights(m, 0), pse(m), nse(m);
stack<int> ps, ns;
int max_area = 0;
for(int i = 0; i < n; i++) {
// Update heights for the current row
for(int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == '1' ? heights[j] + 1 : 0);
pse[j] = -1; nse[j] = m;
}
while(!ps.empty()) ps.pop();
while(!ns.empty()) ns.pop();
// Calculate Next Smaller and Previous Smaller using Monotonic Stacks
for(int j = 0; j < m; j++) {
while(!ns.empty() && heights[ns.top()] > heights[j]) {
nse[ns.top()] = j;
ns.pop();
}
ns.push(j);
while(!ps.empty() && heights[ps.top()] >= heights[j]) {
ps.pop();
}
pse[j] = (ps.empty() ? -1 : ps.top());
ps.push(j);
}
// Calculate max area for this row's histogram
for(int j = 0; j < m; j++) {
max_area = max(max_area, heights[j] * (nse[j] - pse[j] - 1));
}
}
return max_area;
}
};
Python Solution
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
rows = len(matrix)
cols = len(matrix[0])
heights = [0] * cols
max_area = 0
for i in range(rows):
# Update heights based on current row
for j in range(cols):
heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
# Solve Largest Rectangle in Histogram for current row
stack = []
pse = [-1] * cols
nse = [cols] * cols
for j in range(cols):
# Finding Next Smaller Element
while stack and heights[stack[-1]] > heights[j]:
nse[stack.pop()] = j
stack.append(j)
stack = []
for j in range(cols - 1, -1, -1):
# Finding Previous Smaller Element (backwards pass)
while stack and heights[stack[-1]] > heights[j]:
pse[stack.pop()] = j
stack.append(j)
for j in range(cols):
area = heights[j] * (nse[j] - pse[j] - 1)
max_area = max(max_area, area)
return max_area
JavaScript Solution
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
if (matrix.length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
let heights = new Array(cols).fill(0);
let maxArea = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
}
let stack = [];
let nse = new Array(cols).fill(cols);
let pse = new Array(cols).fill(-1);
// Use a single pass or two passes for NSE and PSE
for (let j = 0; j < cols; j++) {
while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[j]) {
nse[stack.pop()] = j;
}
if (stack.length > 0) {
pse[j] = heights[stack[stack.length - 1]] === heights[j]
? pse[stack[stack.length - 1]]
: stack[stack.length - 1];
}
stack.push(j);
}
for (let j = 0; j < cols; j++) {
maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
}
}
return maxArea;
};
Key Takeaways
- Problem Reduction: Learning to see a 2D problem as a sequence of 1D problems (histograms) is a powerful mental model.
- Monotonic Stacks: These are essential for finding the "nearest smaller" or "nearest larger" elements in time.
- Space-Time Tradeoff: By using extra space for heights and stacks, we achieve a total time complexity of , which is much faster than a brute-force approach.
Final Thoughts
This problem is a staple in high-level technical interviews because it combines several layers of logic. In real-world engineering, these techniques are used in Computer Vision for object detection, in Database Optimization for finding contiguous blocks of free space, and in UI Rendering for layout engines. Mastering the monotonic stack will make you a much more formidable problem solver.
Top comments (0)