85. Maximal Rectangle

Hard

Problem Description

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.

Examples

Example 1:
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 shown in the above picture.

Example 2:
Input: matrix = [["0"]]
Output: 0

Example 3:
Input: matrix = [["1"]]
Output: 1
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def maximalRectangle(matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    
    def largestRectangleArea(heights):
        stack = []  # (index, height)
        max_area = 0
        heights = [0] + heights + [0]
        
        for i, height in enumerate(heights):
            start = i
            while stack and stack[-1][1] > height:
                index, h = stack.pop()
                width = i - index
                max_area = max(max_area, width * h)
                start = index
            stack.append((start, height))
        
        return max_area
    
    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0
    
    for row in range(rows):
        # Update heights
        for col in range(cols):
            if matrix[row][col] == "1":
                heights[col] += 1
            else:
                heights[col] = 0
        
        # Calculate max area for current row
        max_area = max(max_area, largestRectangleArea(heights))
    
    return max_area

Java Solution


class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] heights = new int[cols];
        int maxArea = 0;
        
        for (int row = 0; row < rows; row++) {
            // Update heights
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                } else {
                    heights[col] = 0;
                }
            }
            
            // Calculate max area for current row
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack stack = new Stack<>();
        int maxArea = 0;
        int[] h = new int[heights.length + 2];
        
        System.arraycopy(heights, 0, h, 1, heights.length);
        
        for (int i = 0; i < h.length; i++) {
            while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
                int height = h[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

C++ Solution


class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return 0;
        }
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector heights(cols);
        int maxArea = 0;
        
        for (int row = 0; row < rows; row++) {
            // Update heights
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                } else {
                    heights[col] = 0;
                }
            }
            
            // Calculate max area for current row
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector& heights) {
        stack st;
        int maxArea = 0;
        
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                int height = heights[st.top()];
                st.pop();
                int width = i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        
        return maxArea;
    }
};

JavaScript Solution


/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (!matrix.length || !matrix[0].length) {
        return 0;
    }
    
    const largestRectangleArea = (heights) => {
        const stack = [];  // [index, height]
        let maxArea = 0;
        heights = [0, ...heights, 0];
        
        for (let i = 0; i < heights.length; i++) {
            let start = i;
            while (stack.length && stack[stack.length - 1][1] > heights[i]) {
                const [index, height] = stack.pop();
                const width = i - index;
                maxArea = Math.max(maxArea, width * height);
                start = index;
            }
            stack.push([start, heights[i]]);
        }
        
        return maxArea;
    };
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;
    
    for (let row = 0; row < rows; row++) {
        // Update heights
        for (let col = 0; col < cols; col++) {
            if (matrix[row][col] === '1') {
                heights[col]++;
            } else {
                heights[col] = 0;
            }
        }
        
        // Calculate max area for current row
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    
    return maxArea;
};

C# Solution


public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }
        
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        int[] heights = new int[cols];
        int maxArea = 0;
        
        for (int row = 0; row < rows; row++) {
            // Update heights
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                } else {
                    heights[col] = 0;
                }
            }
            
            // Calculate max area for current row
            maxArea = Math.Max(maxArea, LargestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
    private int LargestRectangleArea(int[] heights) {
        Stack stack = new Stack();
        int maxArea = 0;
        int[] h = new int[heights.Length + 2];
        
        Array.Copy(heights, 0, h, 1, heights.Length);
        
        for (int i = 0; i < h.Length; i++) {
            while (stack.Count > 0 && h[stack.Peek()] > h[i]) {
                int height = h[stack.Pop()];
                int width = i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            stack.Push(i);
        }
        
        return maxArea;
    }
}

Complexity Analysis

Solution Explanation

This solution converts the 2D problem into multiple 1D histogram problems:

Key points: