Maximal Rectangle

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

Example 1

Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] → Output: 6

Solution Approach

Build height histogram row by row (heights[j] = consecutive 1s above including current row). Apply "Largest Rectangle in Histogram" for each row.

Maintain heights[]: if matrix[i][j]==1: heights[j]++; else heights[j]=0.
For each row: largestRectangleInHistogram(heights).
Track global max.

Java

import java.util.*;

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix[0].length, max = 0;
        int[] heights = new int[n];
        for (char[] row : matrix) {
            for (int j=0;j<n;j++) heights[j] = row[j]=='1' ? heights[j]+1 : 0;
            max = Math.max(max, largestRect(heights));
        }
        return max;
    }
    private int largestRect(int[] h) {
        Deque<Integer> stack = new ArrayDeque<>();
        int max=0, n=h.length;
        for (int i=0;i<=n;i++) {
            int cur=i==n?0:h[i];
            while (!stack.isEmpty()&&h[stack.peek()]>cur) {
                int height=h[stack.pop()], width=stack.isEmpty()?i:i-stack.peek()-1;
                max=Math.max(max,height*width);
            }
            stack.push(i);
        }
        return max;
    }
}

Time Complexity: O(M*N)
Space Complexity: O(N)