Problem
Given a 2D binary matrix of 0s and 1s, find the largest rectangle containing only 1s.
Example
Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6Solution
Treat each row as a histogram of column heights. Apply largest-rectangle-in-histogram per row.
def maximal_rectangle(matrix):
if not matrix: return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, largest_rectangle_in_histogram(heights))
return max_area
def largest_rectangle_in_histogram(h):
stack = []
max_area = 0
h = h + [0]
for i, height in enumerate(h):
while stack and h[stack[-1]] > height:
top = stack.pop()
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h[top] * width)
stack.append(i)
return max_areafunction maximalRectangle(matrix) {
if (!matrix.length) return 0;
const n = matrix[0].length;
const heights = new Array(n).fill(0);
let maxArea = 0;
for (const row of matrix) {
for (let j = 0; j < n; j++) {
heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
}
maxArea = Math.max(maxArea, largestRect(heights));
}
return maxArea;
}
function largestRect(h) {
const stack = [];
let maxArea = 0;
const arr = [...h, 0];
for (let i = 0; i < arr.length; i++) {
while (stack.length && arr[stack[stack.length-1]] > arr[i]) {
const top = stack.pop();
const width = stack.length === 0 ? i : i - stack[stack.length-1] - 1;
maxArea = Math.max(maxArea, arr[top] * width);
}
stack.push(i);
}
return maxArea;
}int largestRect(vector<int> h) {
h.push_back(0);
stack<int> st;
int maxArea = 0;
for (int i = 0; i < h.size(); i++) {
while (!st.empty() && h[st.top()] > h[i]) {
int top = st.top(); st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = max(maxArea, h[top] * width);
}
st.push(i);
}
return maxArea;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int n = matrix[0].size();
vector<int> heights(n, 0);
int maxArea = 0;
for (auto& row : matrix) {
for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
maxArea = max(maxArea, largestRect(heights));
}
return maxArea;
}public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int n = matrix[0].length;
int[] heights = new int[n];
int maxArea = 0;
for (char[] row : matrix) {
for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
maxArea = Math.max(maxArea, largestRect(heights));
}
return maxArea;
}
private int largestRect(int[] h) {
int[] arr = Arrays.copyOf(h, h.length + 1);
Stack<Integer> st = new Stack<>();
int maxArea = 0;
for (int i = 0; i < arr.length; i++) {
while (!st.isEmpty() && arr[st.peek()] > arr[i]) {
int top = st.pop();
int width = st.isEmpty() ? i : i - st.peek() - 1;
maxArea = Math.max(maxArea, arr[top] * width);
}
st.push(i);
}
return maxArea;
}Complexity
- Time: O(m * n)
- Space: O(n)
Explanation
Each row builds heights of 1-columns standing on top of previous 1-columns. The histogram problem then finds the max rectangle for each row’s skyline.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?