MaximalRectangle.java

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

public class MaximalRectangle {
	public int maximalRectangle(char[][] matrix) {
		int rows = matrix.length;
		if (rows == 0)
			return 0;
		int maxArea = 0;
		int cols = matrix[0].length;
		int[][] map = new int[rows][cols];
		for (int j = 0; j < cols; j++) {
			map[0][j] = matrix[0][j] == '0' ? 0 : 1;
		}
		for (int i = 1; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				map[i][j] = matrix[i][j] == '0' ? map[i - 1][j]
						: map[i - 1][j] + 1;
			}
		}
		int[] row = new int[cols];
		for (int i = 0; i < rows; i++) {
			for (int j = i; j < rows; j++) {
				for (int k = 0; k < cols; k++) {
					row[k] = map[j][k] - (i == 0 ? 0 : map[i - 1][k]);
				}
				int count = 0;
				for (int k = 0; k < cols; k++) {
					if (row[k] == j - i + 1) {
						maxArea = Math.max(maxArea, ++count * (j - i + 1));
					} else {
						maxArea = Math.max(maxArea, count * (j - i + 1));
						count = 0;
					}
				}
			}
		}
		return maxArea;
	}
}