Maximum Rectangle Area with All 1s
Solve this Problemmatrix, find the largest rectangle made entirely of 1s and return its area.
Checking every candidate rectangle directly works but re-examines huge overlapping regions over and over. The faster path reframes each row as a bar chart: for every column, track how many 1s have piled up consecutively ending at the current row. That single row's bar chart is exactly the "largest rectangle in a histogram" problem, solvable in one linear pass with a stack that only ever holds increasing bars — pop a bar the moment a shorter one appears, and its width is exactly how far it could have stretched as the tallest bar in its own rectangle. Running that once per row, keeping a running maximum, finds the biggest all-1s rectangle in the whole grid without ever double-checking the same region.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 200 - ◆
every entry of matrix is either 0 or 1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Candidate Rectangle
BruteA rectangle is fully described by its top, bottom, left, and right edges. Try every combination of those four edges, and for each one check whether the whole region inside is 1s — a 2D prefix-sum table makes that check O(1) (the region is "all 1s" exactly when its sum equals its area), so the cost is dominated by how many candidate rectangles there are to check: O(R²) choices of row-pair times O(C²) choices of column-pair.
O(R² · C²)O(R · C)1class Solution {
2 public int maximalRectangle(int[][] matrix) {
3 int rows = matrix.length;
4 if (rows == 0) return 0;
5 int cols = matrix[0].length;
6 int[][] prefix = new int[rows + 1][cols + 1];
7 for (int r = 0; r < rows; r++) {
8 for (int c = 0; c < cols; c++) {
9 prefix[r + 1][c + 1] = matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];
10 }
11 }
12 int maxArea = 0;
13 for (int top = 0; top < rows; top++) {
14 for (int bottom = top; bottom < rows; bottom++) {
15 for (int left = 0; left < cols; left++) {
16 for (int right = left; right < cols; right++) {
17 int height = bottom - top + 1;
18 int width = right - left + 1;
19 int sum = prefix[bottom + 1][right + 1] - prefix[top][right + 1] - prefix[bottom + 1][left] + prefix[top][left];
20 if (sum == height * width) {
21 maxArea = Math.max(maxArea, height * width);
22 }
23 }
24 }
25 }
26 }
27 return maxArea;
28 }
29}Optimal — Histogram Height per Row + Monotonic Stack
OptimalTurn each row into a bar chart: heights[c] counts how many 1s have stacked up in column c ending at this row (0 the moment a 0 breaks the run). Reading that one row's bar chart as "largest rectangle in a histogram" — solvable in O(C) with a stack that only ever holds increasing heights — accounts for every all-1s rectangle whose bottom edge is this row. Doing that once per row, updating a running maximum, covers every possible rectangle in the whole grid without ever re-checking the same region twice.
O(R · C)O(C)1class Solution {
2 public int maximalRectangle(int[][] matrix) {
3 int rows = matrix.length;
4 if (rows == 0) return 0;
5 int cols = matrix[0].length;
6 int[] heights = new int[cols];
7 int maxArea = 0;
8 for (int r = 0; r < rows; r++) {
9 for (int c = 0; c < cols; c++) {
10 heights[c] = matrix[r][c] == 1 ? heights[c] + 1 : 0;
11 }
12 maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
13 }
14 return maxArea;
15 }
16
17 private int largestRectangleInHistogram(int[] heights) {
18 Deque<Integer> stack = new ArrayDeque<>();
19 int maxArea = 0;
20 int n = heights.length;
21 for (int i = 0; i <= n; i++) {
22 int h = (i == n) ? 0 : heights[i];
23 while (!stack.isEmpty() && heights[stack.peek()] >= h) {
24 int height = heights[stack.pop()];
25 int width = stack.isEmpty() ? i : i - stack.peek() - 1;
26 maxArea = Math.max(maxArea, height * width);
27 }
28 stack.push(i);
29 }
30 return maxArea;
31 }
32}