Leetcode – Maximal Rectangle solution 1 (Java)
Maximum Rectangle area for a 0 1 matrix.
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
ones[][], where ones[i][j] means the number of continuous 1s to the cell matrix[i][j] in jth column. See the following figure. 
|
1 2 3 4 5 |
ones[2][3] = 2 // there are two continuous 1s to cell[2][3] for column 3. ones[3][3] = 3 // there are three continuous 1s to cell[3][3] for column 3. ones[2][2] = 1 // there are one 1 to cell[2][2] for column 2. |
We can fill up the matrix ones[][] using dynamic programming. The formula is :
|
1 2 3 4 5 6 |
for i == 0, ones[0][j] = matrix[0][j] - '0' for i >= 1: if matrix[i][j] == '1', then ones[i][j] = ones[i - 1][j] + 1 else ones[i][j] = 0 |
How to use the ones[][] matrix to calculate the maximum area? From the figure, we know that each row of the new matrix ones[][] actually denotes a histogram. So this problem can be converted to the Largest Rectangle in Histogram Problem.
For the Largest Rectangle in Histogram Problem, there is a O(n) method based on stack. It might be hard to come up with this optimal solution in an interview. Here I describe an easier to understand method.
The idea is to calculate the largest area with the height of ones[i][j] for each position at row i, column j.
For example, suppose we stand on the cell[i][j], ones[i][j] is the current height. Then we expand to the left and right until the height is less than the current height.
For example, in the above figure, ones[3][2] = 2, we want to build a rectangle with height == 2, so we expand to the left. It turns out that ones[3][1] = 0, that means the left area can not be used to form such a rectangle with height == 2. Then we expand to the right, as ones[3][3] == 3, we know the right part can be used to form this rectangle. So with height == 2, 2 is the maximal width to build a rectangle. The corresponding area is 4.
The following is the implementation for the expanding algorithm:
|
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 |
public class MaximalArea { static int maxArea(int[] hist, int i) { int left = i - 1; int right = i + 1; int curHeight = hist[i]; while (left >= 0) { if (hist[left] >= curHeight) { left--; } else { break; } } while (right < hist.length) { if (hist[right] >= curHeight) { right++; } else { break; } } int width = right - left - 1; return curHeight * width; } public static void main(String[] args) { int[] hist = {1, 2, 3, 4, 5}; System.out.println(maxArea(hist, 0)); System.out.println(maxArea(hist, 1)); System.out.println(maxArea(hist, 2)); System.out.println(maxArea(hist, 3)); System.out.println(maxArea(hist, 4)); } } |
The complemented implementation is as follows:
|
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
public class MaximalArea { static int maxArea(int[] hist, int i) { int left = i - 1; int right = i + 1; int curHeight = hist[i]; while (left >= 0) { if (hist[left] >= curHeight) { left--; } else { break; } } while (right < hist.length) { if (hist[right] >= curHeight) { right++; } else { break; } } int width = right - left - 1; return curHeight * width; } static int maxArea(char[][] matrix) { int rowSize = matrix.length; if(rowSize == 0) { return 0; } int columnSize = matrix[0].length; int[][] ones = new int[rowSize][columnSize]; for(int j = 0; j < columnSize; j++) { ones[0][j] = matrix[0][j] - '0'; } for(int i = 1; i< rowSize; i++) { for(int j = 0; j< columnSize; j++) { if(matrix[i][j] == '1') { ones[i][j] = ones[i - 1][j] + 1; } else { ones[i][j] = 0; } } } int res = 0; for(int i = 0; i < rowSize; i++) { for(int j = 0; j < columnSize; j++) { int curMax = maxArea(ones[i], j); res = Math.max(res, curMax); } } return res; } public static void main(String[] args) { int[] hist = {1, 2, 3, 4, 5}; System.out.println(maxArea(hist, 0)); System.out.println(maxArea(hist, 1)); System.out.println(maxArea(hist, 2)); System.out.println(maxArea(hist, 3)); System.out.println(maxArea(hist, 4)); } } |
Please be noted that, the algorithm described here to calculate the largest rectangle in a histogram is not efficient. The time complexity is O(n^2). Here is a faster algorithm to solve the histogram problem.
