Tags
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
Solution 1: use the same idea of largest rectangle in histogram. for each level of 2D matrix, we calculate the height array based on this level. then use stack to calculate the largest rectangle. so the time complexity of this solution is O(n^3).
public int MaximalRectangle(char[,] matrix) { var maximalRectangle = 0; var row = matrix.GetLength(0); var column = matrix.GetLength(1); var dp = new int[column]; var mystack = new Stack(); for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) { if (matrix[i, j] == '0') { dp[j] = 0; } else { dp[j] += 1; } } for (int j = 0; j < column; j++) { while (mystack.Any() && dp[mystack.Peek()] >= dp[j]) { var top = mystack.Pop(); var previous = mystack.Any() ? mystack.Peek() : -1; maximalRectangle = Math.Max(maximalRectangle, dp[top] * (j - previous - 1)); } mystack.Push(j); } while (mystack.Any()) { var top = mystack.Pop(); var previous = mystack.Any() ? mystack.Peek() : -1; maximalRectangle = Math.Max(maximalRectangle, dp[top] * (top - previous)); } } return maximalRectangle; }
Note: please see here for LargestRectangleArea function.
Solution 2: another brilliant solution. see here for more detailed explanation.
public int MaximalRectangle(char[,] matrix) { var res = 0; var row = matrix.GetLength(0); var column = matrix.GetLength(1); var left = new int[column]; var right = Enumerable.Repeat(column, column).ToArray(); var heights = new int[column]; for (int i = 0; i < row; i++) { var curleft = 0; var curright = column; for (int j = 0; j < column; j++) { if (matrix[i, j] == '0') { heights[j] = 0; } else { heights[j]++; } if (matrix[i, j] == '0') { left[j] = 0; curleft = j + 1; } else { left[j] = Math.Max(left[j], curleft); } } for (int j = column - 1; j >= 0; j--) { if (matrix[i, j] == '0') { right[j] = column; curright = j; } else { right[j] = Math.Min(right[j], curright); } } for (int j = 0; j < column; j++) { res = Math.Max(res, heights[j] * (right[j] - left[j])); } } return res; }