[LeetCode] 85. Maximal Rectangle

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

Thought process:
This problem is similar to 84. Largest Rectangle in Histogram. In that problem, I'm given an array of heights and asked to calculate the largest rectangle that can be formed by the heights. In this problem, I can keep an array of heights, which keeps track of the propagation of heights as I iterate through the matrix row by row. So the problem becomes calculating the largest rectangle in histogram for every row.

Solution 1 (stack):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public class Solution { public int maximalRectangle(char[][] matrix) { int rowLength = matrix.length; if (rowLength == 0) { return 0; } int columnLength = matrix[0].length; Stack<Integer> stack = new Stack<>(); int[] height = new int[columnLength + 1]; height[columnLength] = -1; int max = 0; for (int i = 0; i < rowLength; i++) { for (int j = 0; j <= columnLength; j++) { if (j < columnLength) { if (matrix[i][j] == '0') { height[j] = 0; } else { height[j]++; } } while (!stack.isEmpty() && height[stack.peek()] >= height[j]) { int index = stack.pop(); int width = stack.isEmpty() ? j : j - stack.peek() - 1; max = Math.max(max, width * height[index]); } if (j < columnLength) { stack.push(j); } } } return max; } }

This problem can also be solved using dynamic programming. The sub-problem is to find the maximal rectangle on top of the current cell that has the highest height. A key point here is that we don't care about the rectangles that don't have the maximum height, because those will eventually be covered by some other cell.
To calculate the maximal rectangle at each cell, I need to know the rectangle's left boundary, right boundary, and height. I can iterate through the matrix row by row, and maintain three global arrays left[], right[] and height[]. I also use variables currentLeft and currentRight to mark the left and right boundaries of current iteration. The functions for the arrays are:

left[j] = max(left[j] of the last row, currLeft),
right[j] = min(right[j] of the last row, currRight),
height[j] = 0 if matrix[i][j] == '0',
height[j] = height[j] of the last row + 1 if matrix[i][j] == '1'.

These arrays will propagate downwards as we iterate through the matrix row by row. 

Solution 2 (DP):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class Solution { public int maximalRectangle(char[][] matrix) { int height = matrix.length; if (height == 0) { return 0; } int width = matrix[0].length; int maximal = 0; int[] left = new int[width]; int[] right = new int[width]; int[] heights = new int[width]; Arrays.fill(right, width - 1); for (int i = 0; i < height; i++) { int currentLeft = 0; int currentRight = width - 1; for (int j = 0; j < width; j++) { if (matrix[i][j] == '0') { currentLeft = j + 1; left[j] = 0; heights[j] = 0; } else { left[j] = Math.max(currentLeft, left[j]); heights[j]++; } } for (int j = width - 1; j >= 0; j--) { if (matrix[i][j] == '0') { currentRight = j - 1; right[j] = width - 1; } else { right[j] = Math.min(currentRight, right[j]); } } for (int j = 0; j < width; j++) { maximal = Math.max(maximal, (right[j] - left[j] + 1) * heights[j]); } } return maximal; } }

Time complexity:
Say the height of the matrix is h and width is w. Initialization takes O(w). The nested for loops take O(hw). So the overall time complexity is O(hw).