You are given a binary matrix (a grid) where each cell contains either '0' or '1'. Your task is to find the largest rectangle that contains only '1's in this grid and return its area.
Input: array = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Input: array = [["0"]]
Output: 0
Input: array = [["1"]]
Output: 1
function maximalRectangleHistogram(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const heights = 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;
}
maxArea = Math.max(maxArea, computeLargestRectangleArea(heights));
}
return maxArea;
}
function computeLargestRectangleArea(heights) {
const stack = [];
let maxArea = 0;
let index = 0;
while (index < heights.length) {
if (stack.length === 0 || heights[stack[stack.length - 1]] <= heights[index]) {
stack.push(index++);
} else {
const topOfStack = stack.pop();
const area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
}
while (stack.length > 0) {
const topOfStack = stack.pop();
const area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleHistogram(array1); //output: 6
const array2 = [["0"]];
maximalRectangleHistogram(array2); //output: 0
const array3 = [["1"]];
maximalRectangleHistogram(array3); //output: 1
function maximalRectangleBruteForce(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let maxArea = 0;
for (let r1 = 0; r1 < rows; r1++) {
for (let c1 = 0; c1 < cols; c1++) {
if (matrix[r1][c1] === '1') {
for (let r2 = r1; r2 < rows; r2++) {
for (let c2 = c1; c2 < cols; c2++) {
if (matrix[r2][c2] === '1') {
let valid = true;
for (let r = r1; r <= r2; r++) {
for (let c = c1; c <= c2; c++) {
if (matrix[r][c] !== '1') {
valid = false;
break;
}
}
if (!valid) break;
}
if (valid) {
maxArea = Math.max(maxArea, (r2 - r1 + 1) * (c2 - c1 + 1));
}
}
}
}
}
}
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleBruteForce(array1); //output: 6
const array2 = [["0"]];
maximalRectangleBruteForce(array2); //output: 0
const array3 = [["1"]];
maximalRectangleBruteForce(array3); //output: 1
function maximalRectanglePrefixSum(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const prefixSum = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
let maxArea = 0;
for (let i = 1; i <= rows; i++) {
for (let j = 1; j <= cols; j++) {
prefixSum[i][j] = parseInt(matrix[i - 1][j - 1]) +
prefixSum[i - 1][j] +
prefixSum[i][j - 1] -
prefixSum[i - 1][j - 1];
}
}
for (let r1 = 1; r1 <= rows; r1++) {
for (let c1 = 1; c1 <= cols; c1++) {
for (let r2 = r1; r2 <= rows; r2++) {
for (let c2 = c1; c2 <= cols; c2++) {
const area = (r2 - r1 + 1) * (c2 - c1 + 1);
const total = prefixSum[r2][c2] - prefixSum[r1 - 1][c2] -
prefixSum[r2][c1 - 1] + prefixSum[r1 - 1][c1 - 1];
if (total === area) {
maxArea = Math.max(maxArea, area);
}
}
}
}
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectanglePrefixSum(array1); //output: 6
const array2 = [["0"]];
maximalRectanglePrefixSum(array2); //output: 0
const array3 = [["1"]];
maximalRectanglePrefixSum(array3); //output: 1
function maximalRectangleDP2D(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
let maxArea = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] === '1') {
dp[i][j] = (i === 0 ? 1 : dp[i - 1][j] + 1);
let minHeight = dp[i][j];
for (let k = j; k >= 0; k--) {
minHeight = Math.min(minHeight, dp[i][k]);
maxArea = Math.max(maxArea, minHeight * (j - k + 1));
}
}
}
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleDP2D(array1); //output: 6
const array2 = [["0"]];
maximalRectangleDP2D(array2); //output: 0
const array3 = [["1"]];
maximalRectangleDP2D(array3); //output: 1
function maximalRectangleStack(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const heights = Array(cols).fill(0);
let maxArea = 0;
for (let i = 0; i < rows; i++) {
// Update histogram heights for the current row
for (let j = 0; j < cols; j++) {
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
}
// Calculate the maximum rectangle area for the updated histogram heights
maxArea = Math.max(maxArea, maxRectangleInHistogram(heights));
}
return maxArea;
}
function maxRectangleInHistogram(heights) {
const stack = [];
let maxArea = 0;
let index = 0;
while (index < heights.length) {
if (stack.length === 0 || heights[index] >= heights[stack[stack.length - 1]]) {
stack.push(index++);
} else {
const topOfStack = stack.pop();
const height = heights[topOfStack];
const width = stack.length === 0 ? index : index - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
}
while (stack.length > 0) {
const topOfStack = stack.pop();
const height = heights[topOfStack];
const width = stack.length === 0 ? index : index - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleStack(array1); //output: 6
const array2 = [["0"]];
maximalRectangleStack(array2); //output: 0
const array3 = [["1"]];
maximalRectangleStack(array3); //output: 1
function maximalRectangleBinarySearch(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
// Binary search on area
let left = 0;
let right = rows * cols;
let maxArea = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canFormRectangle(matrix, mid)) {
maxArea = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return maxArea;
}
function canFormRectangle(matrix, area) {
const rows = matrix.length;
const cols = matrix[0].length;
const minHeight = Math.ceil(area / cols);
// Construct height matrix
const heights = Array.from({ length: rows }, () => Array(cols).fill(0));
for (let i = 0; i < cols; i++) {
heights[0][i] = matrix[0][i] === '1' ? 1 : 0;
for (let r = 1; r < rows; r++) {
heights[r][i] = matrix[r][i] === '1' ? heights[r - 1][i] + 1 : 0;
}
}
// Check if there's a rectangle with at least the given area
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (heights[r][c] >= minHeight) {
let width = 0;
for (let k = c; k >= 0; k--) {
if (heights[r][k] < minHeight) break;
width++;
if (width * minHeight >= area) return true;
}
}
}
}
return false;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleBinarySearch(array1); //output: 6
const array2 = [["0"]];
maximalRectangleBinarySearch(array2); //output: 0
const array3 = [["1"]];
maximalRectangleBinarySearch(array3); //output: 1
function maximalRectangleDP(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array.from({ length: rows }).map(() => Array(cols).fill(0));
let maxArea = 0;
// Calculate dp table
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] === '1') {
dp[i][j] = (j === 0 ? 1 : dp[i][j - 1] + 1);
} else {
dp[i][j] = 0;
}
}
}
// Compute the maximum rectangle area
for (let j = 0; j < cols; j++) {
let stack = [];
for (let i = 0; i < rows; i++) {
while (stack.length > 0 && dp[i][j] < dp[stack[stack.length - 1]][j]) {
const height = dp[stack.pop()][j];
const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
while (stack.length > 0) {
const height = dp[stack.pop()][j];
const width = stack.length === 0 ? rows : rows - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleDP(array1); //output: 6
const array2 = [["0"]];
maximalRectangleDP(array2); //output: 0
const array3 = [["1"]];
maximalRectangleDP(array3); //output: 1
function maximalRectangleRowPrefix(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let maxArea = 0;
const heights = Array(cols).fill(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;
}
maxArea = Math.max(maxArea, computeAreaInHistogram(heights));
}
return maxArea;
}
function computeAreaInHistogram(heights) {
const stack = [];
let maxArea = 0;
let index = 0;
while (index < heights.length) {
if (stack.length === 0 || heights[stack[stack.length - 1]] <= heights[index]) {
stack.push(index++);
} else {
const topOfStack = stack.pop();
const area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
}
while (stack.length > 0) {
const topOfStack = stack.pop();
const area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleRowPrefix(array1); //output: 6
const array2 = [["0"]];
maximalRectangleRowPrefix(array2); //output: 0
const array3 = [["1"]];
maximalRectangleRowPrefix(array3); //output: 1
function maximalRectangleBottomUpApproach(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const heights = Array(cols).fill(0);
let maxArea = 0;
for (let i = 0; i < rows; i++) {
// Update histogram heights
for (let j = 0; j < cols; j++) {
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
}
// Calculate the maximal rectangle for the current histogram
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
function largestRectangleArea(heights) {
const stack = [];
let maxArea = 0;
let index = 0;
while (index < heights.length) {
if (stack.length === 0 || heights[stack[stack.length - 1]] <= heights[index]) {
stack.push(index++);
} else {
const topOfStack = stack.pop();
const height = heights[topOfStack];
const width = stack.length === 0 ? index : index - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
}
while (stack.length > 0) {
const topOfStack = stack.pop();
const height = heights[topOfStack];
const width = stack.length === 0 ? index : index - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleBottomUpApproach(array1); //output: 6
const array2 = [["0"]];
maximalRectangleBottomUpApproach(array2); //output: 0
const array3 = [["1"]];
maximalRectangleBottomUpApproach(array3); //output: 1
function maximalRectangleTransform(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let maxArea = 0;
const heights = Array(cols).fill(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;
}
maxArea = Math.max(maxArea, computeLargestRect(heights));
}
return maxArea;
}
function computeLargestRect(heights) {
const stack = [];
let maxArea = 0;
let index = 0;
while (index < heights.length) {
if (stack.length === 0 || heights[stack[stack.length - 1]] <= heights[index]) {
stack.push(index++);
} else {
const topOfStack = stack.pop();
const area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
}
while (stack.length > 0) {
const topOfStack = stack.pop();
const area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
const array1 = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]];
maximalRectangleTransform(array1); //output: 6
const array2 = [["0"]];
maximalRectangleTransform(array2); //output: 0
const array3 = [["1"]];
maximalRectangleTransform(array3); //output: 1