85. Maximal Rectangle

Description

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : O(row*column)
 * Space complexity : O(column)
 */

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || 
           matrix.length == 0 || 
           matrix[0].length == 0) return 0;
        
        int m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n];
        
        int maxRect = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int value = matrix[i][j]-'0';
                heights[j] = (value == 0)? 0: (value + heights[j]);
            }
            maxRect = Math.max(maxRect, largestRectangleArea(heights));
        }
        return maxRect;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, area = 0;
        
        while(i < heights.length) {
            if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.add(i++);
            } else {
                area = Math.max(area, calculateArea(stack, heights, i));
            }
        }
        
        while(!stack.isEmpty()) {
            area = Math.max(area, calculateArea(stack, heights, i));
        }
        
        return area;
    }

    private int calculateArea(Stack<Integer> stack, int[] heights, int i) {
        int height = heights[stack.pop()];
        int weight = (stack.isEmpty())? i: (i-stack.peek()-1);
        return height * weight;
    }
}

Follow up