Course4all

Maximal Rectangle

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

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) { ... }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLargest Rectangle in Histogram
Next Question →Trapping Rain Water