Maximal Rectangle Problem
The “Maximal Rectangle” problem is a classical algorithmic challenge where you are given a 2D binary matrix filled with 0‘s and 1‘s. The goal is to find the largest rectangle containing only 1‘s and return its area.
Problem Statement:
Given a binary matrix, find the area of the largest rectangle containing only 1s.
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 the rectangle with the bottom-right corner at matrix[2][2], spanning 3 columns and 2 rows. Therefore, the area is 3 * 2 = 6.
Approach:
- Transform the Problem: Each row in the matrix can be treated as the base of a histogram where the heights of the bars are the number of consecutive
1s up to that row. - Dynamic Programming (DP) + Histogram:
- Convert the 2D matrix into a histogram where the height of each column increases as you move down the rows if the cell is
1. - For each row, calculate the largest rectangle possible in the histogram formed by the heights of the bars up to that row.
- Convert the 2D matrix into a histogram where the height of each column increases as you move down the rows if the cell is
- Find Max Area in Histogram:
- For each row, use a stack-based approach to calculate the largest rectangle in a histogram in O(m) time where m is the number of columns.
- Time Complexity:
- Building the histogram takes O(n * m) where n is the number of rows and m is the number of columns.
- The stack-based approach to find the maximal rectangle in the histogram also runs in O(m) for each row.
- Overall time complexity is O(n * m).
- Space Complexity: O(m) where m is the number of columns for storing the heights.
Algorithm:
- Convert each row to a histogram by updating heights (based on whether the current cell is
1or0). - For each row, compute the maximum rectangle area using a stack-based method to calculate the largest rectangle in the histogram.
- Update the result for the maximum area.
Code Implementation in Different Languages:
C:
#include <stdio.h>
#include <stdlib.h>
int maxHistArea(int *hist, int m) {
int *stack = (int *)malloc(m * sizeof(int));
int top = -1, maxArea = 0, area = 0, i = 0;
while (i < m) {
if (top == -1 || hist[stack[top]] <= hist[i]) {
stack[++top] = i++;
} else {
int height = hist[stack[top--]];
int width = (top == -1) ? i : i - stack[top] - 1;
area = height * width;
maxArea = (maxArea > area) ? maxArea : area;
}
}
while (top >= 0) {
int height = hist[stack[top--]];
int width = (top == -1) ? i : i - stack[top] - 1;
area = height * width;
maxArea = (maxArea > area) ? maxArea : area;
}
free(stack);
return maxArea;
}
int maximalRectangle(char **matrix, int n, int m) {
int *heights = (int *)calloc(m, sizeof(int));
int maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
int area = maxHistArea(heights, m);
maxArea = (maxArea > area) ? maxArea : area;
}
free(heights);
return maxArea;
}
int main() {
char *matrix[] = {
"10100",
"10111",
"11111",
"10010"
};
int n = 4, m = 5;
printf("Maximal Rectangle Area: %d\n", maximalRectangle(matrix, n, m));
return 0;
}
C++:
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int maxHistArea(vector<int>& hist, int m) {
stack<int> st;
int maxArea = 0, area = 0, i = 0;
while (i < m) {
if (st.empty() || hist[st.top()] <= hist[i]) {
st.push(i++);
} else {
int height = hist[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
area = height * width;
maxArea = max(maxArea, area);
}
}
while (!st.empty()) {
int height = hist[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
area = height * width;
maxArea = max(maxArea, area);
}
return maxArea;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<int> heights(m, 0);
int maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
maxArea = max(maxArea, maxHistArea(heights, m));
}
return maxArea;
}
int main() {
vector<vector<char>> matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
cout << "Maximal Rectangle Area: " << maximalRectangle(matrix) << endl;
return 0;
}
Java:
import java.util.Stack;
public class MaximalRectangle {
public static int maxHistArea(int[] hist, int m) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0, area = 0, i = 0;
while (i < m) {
if (stack.isEmpty() || hist[stack.peek()] <= hist[i]) {
stack.push(i++);
} else {
int height = hist[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
area = height * width;
maxArea = Math.max(maxArea, area);
}
}
while (!stack.isEmpty()) {
int height = hist[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
area = height * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
public static int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int n = matrix.length, m = matrix[0].length;
int[] heights = new int[m];
int maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
maxArea = Math.max(maxArea, maxHistArea(heights, m));
}
return maxArea;
}
public static void main(String[] args) {
char[][] matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
System.out.println("Maximal Rectangle Area: " + maximalRectangle(matrix));
}
}
Python:
def maxHistArea(heights):
stack = []
max_area = 0
i = 0
while i < len(heights):
if not stack or heights[stack[-1]] <= heights[i]:
stack.append(i)
i += 1
else:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
while stack:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
return max_area
def maximalRectangle(matrix):
if not matrix:
return 0
n, m = len(matrix), len(matrix[0])
heights = [0] * m
max_area = 0
for i in range(n):
for j in range(m):
heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
max_area = max(max_area, maxHistArea(heights))
return max_area
# Example Usage
matrix = [
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
]
print("Maximal Rectangle Area:", maximalRectangle(matrix))
C#:
using System;
using System.Collections.Generic;
public class MaximalRectangle {
public static int MaxHistArea(int[] hist, int m) {
Stack<int> stack = new Stack<int>();
int maxArea = 0, area = 0, i = 0;
while (i < m) {
if (stack.Count == 0 || hist[stack.Peek()] <= hist[i]) {
stack.Push(i++);
} else {
int height = hist[stack.Pop()];
int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
area = height * width;
maxArea = Math.Max(maxArea, area);
}
}
while (stack.Count > 0) {
int height = hist[stack.Pop()];
int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
area = height * width;
maxArea = Math.Max(maxArea, area);
}
return maxArea;
}
public static int MaximalRectangle(char[][] matrix) {
if (matrix.Length == 0) return 0;
int n = matrix.Length, m = matrix[0].Length;
int[] heights = new int[m];
int maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
maxArea = Math.Max(maxArea, MaxHistArea(heights, m));
}
return maxArea;
}
public static void Main() {
char[][] matrix = {
new char[] {'1', '0', '1', '0', '0'},
new char[] {'1', '0', '1', '1', '1'},
new char[] {'1', '1', '1', '1', '1'},
new char[] {'1', '0', '0', '1', '0'}
};
Console.WriteLine("Maximal Rectangle Area: " + MaximalRectangle(matrix));
}
}
JavaScript:
function maxHistArea(heights) {
let stack = [];
let maxArea = 0, area = 0, i = 0;
while (i < heights.length) {
if (stack.length === 0 || heights[stack[stack.length - 1]] <= heights[i]) {
stack.push(i++);
} else {
let h = heights[stack.pop()];
let w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, h * w);
}
}
while (stack.length > 0) {
let h = heights[stack.pop()];
let w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, h * w);
}
return maxArea;
}
function maximalRectangle(matrix) {
if (!matrix.length) return 0;
let n = matrix.length, m = matrix[0].length;
let heights = new Array(m).fill(0);
let maxArea = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
heights[j] = (matrix[i][j] === '1') ? heights[j] + 1 : 0;
}
maxArea = Math.max(maxArea, maxHistArea(heights));
}
return maxArea;
}
// Example Usage
let matrix = [
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
];
console.log("Maximal Rectangle Area:", maximalRectangle(matrix));
Summary:
- Time Complexity: O(n * m), where n is the number of rows and m is the number of columns.
- Space Complexity: O(m), where m is the number of columns (for storing heights).