Course4all
Join us on telegram
Home/dsa/Stack/Maximal Rectangle

Maximal Rectangle

Master this topic with zero to advance depth.

Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Visual Representation

Matrix: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Row 0: [1, 0, 1, 0, 0] -> Hist Max: 1 Row 1: [2, 0, 2, 1, 1] -> Hist Max: 2 Row 2: [3, 1, 3, 2, 2] -> Hist Max: 6 (The answer) Row 3: [4, 0, 0, 3, 0] -> Hist Max: 4
Hard

Examples

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Approach 1

Level III: Optimal (Histogram per Row)

Intuition

This problem is a 2D extension of 'Largest Rectangle in Histogram'. We can treat each row as the base of a histogram where the 'height' of each column is the number of consecutive 1's above it. For each row, we maintain these heights and call the histogram function to find the max rectangle at that row.

⏱ O(Rows * Cols)💾 O(Cols)
java
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (char[] row : matrix) {
            for (int i = 0; i < row.length; i++) {
                heights[i] = row[i] == '1' ? heights[i] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
    // reused logic from Largest Rectangle in Histogram
    private int largestRectangleArea(int[] heights) { ... }
}
← Previous QuestionLargest Rectangle in Histogram
Next Question →Trapping Rain Water