LeetCode 85: Maximal Rectangle Solution

Master LeetCode problem 85 (Maximal Rectangle), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

85. Maximal Rectangle

Hard

Array Dynamic Programming Stack Matrix Monotonic Stack

Problem Explanation

Explanation

To solve this problem, we can apply the concept of the "Largest Rectangle in Histogram" problem. We can treat each row of the matrix as the base of a histogram, where each column contributes to the height of the histogram. By maintaining a histogram for each row and updating it based on the current row and the previous histogram, we can find the maximal rectangle containing only 1's.

The algorithm involves iterating through each row of the matrix and treating it as the base of the histogram. At each row, we update the histogram by incrementing the height if the current cell is '1', or setting the height to 0 if the current cell is '0'. Then, we calculate the maximal rectangle area based on the updated histogram.

The time complexity of this algorithm is O(rows * cols) as we iterate through each element in the matrix. The space complexity is O(cols) for storing the histogram.

Solution Code

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 maxArea = 0;
        int[] heights = new int[cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        
        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length) ? 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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 85 (Maximal Rectangle)?

This page provides optimized solutions for LeetCode problem 85 (Maximal Rectangle) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 85 (Maximal Rectangle)?

The time complexity for LeetCode 85 (Maximal Rectangle) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 85 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 85 in Java, C++, or Python.

Back to LeetCode Solutions