LeetCode Hard – 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.

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

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'.

Java Solution

To solve this problem, you can use the concept of the largest rectangle in histogram for each row in the matrix. You iterate through each row of the matrix, treating it as a histogram, and for each row, you calculate the largest rectangle area using the histogram algorithm. The final answer is the maximum area obtained across all rows. Here’s the Java code for the solution:

public class MaximalRectangle {
    public static 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 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 static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;

        for (int i = 0; i <= heights.length; i++) {
            int currentHeight = (i == heights.length) ? 0 : heights[i];

            while (!stack.isEmpty() && currentHeight < 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;
    }

    public static void main(String[] args) {
        char[][] matrix1 = {
            {'1', '0', '1', '0', '0'},
            {'1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '0'}
        };
        System.out.println(maximalRectangle(matrix1));  // Output: 6

        char[][] matrix2 = {
            {'0'}
        };
        System.out.println(maximalRectangle(matrix2));  // Output: 0

        char[][] matrix3 = {
            {'1'}
        };
        System.out.println(maximalRectangle(matrix3));  // Output: 1
    }
}

This Java code defines a maximalRectangle method that takes a binary matrix as input and returns the area of the largest rectangle containing only 1’s. The largestRectangleArea method is used for calculating the largest rectangle area for each row. The provided test cases demonstrate its usage.

Python Solution

Here’s the Python solution for finding the largest rectangle containing only 1’s in a binary matrix:

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0

    for i in range(rows):
        for j in range(cols):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

        max_area = max(max_area, largestRectangleArea(heights))

    return max_area

def largestRectangleArea(heights):
    stack = []
    max_area = 0

    for i in range(len(heights) + 1):
        current_height = heights[i] if i < len(heights) else 0

        while stack and current_height < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area

# Test cases
matrix1 = [
    ['1', '0', '1', '0', '0'],
    ['1', '0', '1', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['1', '0', '0', '1', '0']
]
print(maximalRectangle(matrix1))  # Output: 6

matrix2 = [['0']]
print(maximalRectangle(matrix2))  # Output: 0

matrix3 = [['1']]
print(maximalRectangle(matrix3))  # Output: 1

This Python code follows the same logic as the Java solution. The maximalRectangle function takes a binary matrix as input and returns the area of the largest rectangle containing only 1’s. The largestRectangleArea function is used to calculate the largest rectangle area for each row. The provided test cases demonstrate its usage.