MatrixProblem 6 of 10
Maximum size rectangle
Problem Statement
Given a binary matrix (containing only 0s and 1s), find the maximum area of a 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 maximum rectangle has area 6 (rows 1-2, columns 2-4).
Approach 1: Brute Force (Check All Rectangles)
Intuition
For every possible pair of top-left and bottom-right corners, check if the rectangle contains only 1s and track the maximum area.
Algorithm
- For each cell as top-left corner
- For each cell as bottom-right corner
- Check if all cells in rectangle are 1s
- Track maximum area
java
public class Solution {
private boolean isAllOnes(int[][] matrix, int r1, int c1, int r2, int c2) {
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
if (matrix[i][j] == 0) return false;
}
}
return true;
}
public int maxRectangleBrute(int[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int maxArea = 0;
// Try all possible rectangles
for (int r1 = 0; r1 < m; r1++) {
for (int c1 = 0; c1 < n; c1++) {
for (int r2 = r1; r2 < m; r2++) {
for (int c2 = c1; c2 < n; c2++) {
if (isAllOnes(matrix, r1, c1, r2, c2)) {
int area = (r2 - r1 + 1) * (c2 - c1 + 1);
maxArea = Math.max(maxArea, area);
}
}
}
}
}
return maxArea;
}
}Complexity Analysis
- Time Complexity: O(m^2 * n^2 * m * n) = O(m^3 * n^3) - Can be optimized to O(m^2 * n^2) with prefix sums
- Space Complexity: O(1)
Approach 2: Histogram Based (Optimal)
Intuition
Convert each row into a histogram problem. For each row, treat consecutive 1s as bars of a histogram (height = count of consecutive 1s above including current row). Then find the largest rectangle in this histogram.
Algorithm
- Build height array row by row
- If matrix[i][j] == 1, height[j]++
- If matrix[i][j] == 0, height[j] = 0
- For each row, find largest rectangle in histogram using stack
- Track maximum area across all rows
java
import java.util.*;
public class Solution {
private int largestRectangleInHistogram(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && h < heights[stack.peek()]) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
public int maximalRectangle(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int maxArea = 0;
for (int i = 0; i < m; i++) {
// Update heights for current row
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) {
heights[j]++;
} else {
heights[j] = 0;
}
}
// Find largest rectangle in this histogram
maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
}
return maxArea;
}
}Complexity Analysis
- Time Complexity: O(m * n) - Process each cell once, histogram solution is O(n)
- Space Complexity: O(n) - Height array and stack
Understanding the Histogram Approach
Matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Heights after each row:
Row 0: [1, 0, 1, 0, 0] -> Max rect = 1
Row 1: [2, 0, 2, 1, 1] -> Max rect = 3 (height 1, width 3)
Row 2: [3, 1, 3, 2, 2] -> Max rect = 6 (height 2, width 3) <-- ANSWER
Row 3: [4, 0, 0, 3, 0] -> Max rect = 4 (height 4, width 1)
Largest Rectangle in Histogram - Detailed
The stack-based approach maintains indices of bars in increasing height order:
- If current bar is taller, push to stack
- If current bar is shorter, pop and calculate area
- Width = distance to previous smaller element
Key Takeaways
- Reducing to histogram problem is a powerful technique for 2D problems
- The histogram approach uses stack to find next/previous smaller elements
- Each cell is visited constant number of times (push once, pop once)
- This technique applies to: maximal rectangle, largest submatrix with equal rows, etc.
- The key insight: heights reset to 0 when we encounter a 0
- Understanding "Largest Rectangle in Histogram" is prerequisite for this problem
- Similar approach works for "Maximal Square" problem using DP