Problem
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
Solution
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
var n = matrix.length;
var m = (matrix[0] || []).length;
var max = 0;
var heights = Array(m);
var stack = [];
var h = 0;
var w = 0;
for (var i = 0; i < n; i++) {
stack = [];
for (var j = 0; j < m; j++) {
if (matrix[i][j] === '1') {
heights[j] = i === 0 ? 1 : heights[j] + 1;
} else {
heights[j] = 0;
}
while (stack.length && heights[j] <= heights[stack[stack.length - 1]]) {
h = heights[stack.pop()];
w = stack.length === 0 ? j : j - stack[stack.length - 1] - 1;
max = Math.max(max, h * w);
}
stack.push(j);
}
while (stack.length) {
h = heights[stack.pop()];
w = stack.length === 0 ? m : m - stack[stack.length - 1] - 1;
max = Math.max(max, h * w);
}
}
return max;
};
Explain:
see Largest Rectangle in Histogram.
Complexity:
- Time complexity : O(n^2).
- Space complexity : O(n).