Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximal Rectangle

HARDProblemSolveExternal Links

Description

You are given a two-dimensional binary matrix of size rows x cols. Every cell in this matrix contains either the character '0' or the character '1'.

Your task is to find the largest rectangle that is made up entirely of '1's and return its area (number of cells). The rectangle must be axis-aligned — its sides run horizontally and vertically within the matrix.

If the matrix contains no '1's at all, return 0.

4x5 binary matrix with the maximal 2x3 rectangle of ones highlighted
4x5 binary matrix with the maximal 2x3 rectangle of ones highlighted

Examples

Example 1

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output: 6

Explanation: The matrix looks like:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The largest rectangle containing only 1's spans rows 1-2 and columns 2-4. That is a 2-row by 3-column block, giving an area of 2 × 3 = 6. No larger all-ones rectangle exists in this matrix.

Example 2

Input: matrix = [["0"]]

Output: 0

Explanation: The single cell is '0', so there is no rectangle of 1's at all. The answer is 0.

Example 3

Input: matrix = [["1"]]

Output: 1

Explanation: The single cell is '1'. The only possible rectangle is that 1×1 cell itself, with area 1.

Constraints

  • rows == matrix.length
  • cols == matrix[i].length
  • 1 ≤ rows, cols ≤ 200
  • matrix[i][j] is '0' or '1'

Editorial

Brute Force

Intuition

The most straightforward way to find the largest rectangle of 1's is to consider every possible rectangle in the matrix and check whether all its cells are 1.

A rectangle is defined by choosing a top-left corner (r1, c1) and a bottom-right corner (r2, c2). For every such pair of corners, we scan every cell inside the rectangle to see if any cell is 0. If the entire rectangle is all 1's, we compute its area and track the maximum.

Think of it like trying on every possible picture frame over the matrix — you slide the frame to every position, try every possible width and height, and each time you peek through the frame to check if every cell you see is a 1.

Step-by-Step Explanation

Let's trace through a small 3×3 matrix to illustrate the brute force approach:

matrix = [["1","0","1"],
          ["1","1","1"],
          ["0","1","1"]]

Step 1: Start with top-left corner (0, 0). Try every possible bottom-right corner.

  • Rectangle (0,0)→(0,0): cell is '1'. Area = 1. max_area = 1.
  • Rectangle (0,0)→(0,1): cells are '1','0'. Contains a 0 → invalid.
  • Rectangle (0,0)→(1,0): cells are '1','1'. Area = 2. max_area = 2.
  • Rectangle (0,0)→(1,1): cells include (0,1)='0' → invalid.
  • Rectangle (0,0)→(2,0): cells include (2,0)='0' → invalid.

Step 2: Move top-left to (0, 1).

  • Rectangle (0,1)→(0,1): cell is '0' → invalid.
  • (Any rectangle starting from a '0' cell is automatically invalid.)

Step 3: Move top-left to (0, 2).

  • Rectangle (0,2)→(0,2): cell is '1'. Area = 1.
  • Rectangle (0,2)→(1,2): cells '1','1'. Area = 2.
  • Rectangle (0,2)→(2,2): cells '1','1','1'. Area = 3. max_area = 3.

Step 4: Continue with top-left corners (1,0), (1,1), (1,2), (2,0), (2,1), (2,2), checking all possible rectangles from each.

  • At top-left (1,1), bottom-right (2,2): cells are '1','1','1','1'. Area = 4. max_area = 4.

Step 5: After exhausting all possibilities, return max_area = 4.

The rectangle from (1,1) to (2,2) is the 2×2 block of all 1's — the largest in this matrix.

Algorithm

  1. Initialize max_area = 0.
  2. For each possible top-left corner (r1, c1) where r1 ranges from 0 to rows-1 and c1 from 0 to cols-1:
    a. For each possible bottom-right corner (r2, c2) where r2 ≥ r1 and c2 ≥ c1:
    • Scan every cell (r, c) inside the rectangle [r1..r2][c1..c2].
    • If any cell is '0', this rectangle is invalid — break and try the next.
    • If all cells are '1', compute area = (r2 - r1 + 1) * (c2 - c1 + 1) and update max_area.
  3. Return max_area.

Code

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) return 0;
        int cols = matrix[0].size();
        int maxArea = 0;

        for (int r1 = 0; r1 < rows; r1++) {
            for (int c1 = 0; c1 < cols; c1++) {
                for (int r2 = r1; r2 < rows; r2++) {
                    for (int c2 = c1; c2 < cols; c2++) {
                        bool allOnes = true;
                        for (int r = r1; r <= r2 && allOnes; r++) {
                            for (int c = c1; c <= c2 && allOnes; c++) {
                                if (matrix[r][c] == '0') {
                                    allOnes = false;
                                }
                            }
                        }
                        if (allOnes) {
                            int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                            maxArea = max(maxArea, area);
                        }
                    }
                }
            }
        }
        return maxArea;
    }
};
class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        max_area = 0

        for r1 in range(rows):
            for c1 in range(cols):
                for r2 in range(r1, rows):
                    for c2 in range(c1, cols):
                        all_ones = True
                        for r in range(r1, r2 + 1):
                            for c in range(c1, c2 + 1):
                                if matrix[r][c] == '0':
                                    all_ones = False
                                    break
                            if not all_ones:
                                break
                        if all_ones:
                            area = (r2 - r1 + 1) * (c2 - c1 + 1)
                            max_area = max(max_area, area)
        return max_area
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        int maxArea = 0;

        for (int r1 = 0; r1 < rows; r1++) {
            for (int c1 = 0; c1 < cols; c1++) {
                for (int r2 = r1; r2 < rows; r2++) {
                    for (int c2 = c1; c2 < cols; c2++) {
                        boolean allOnes = true;
                        for (int r = r1; r <= r2 && allOnes; r++) {
                            for (int c = c1; c <= c2 && allOnes; c++) {
                                if (matrix[r][c] == '0') {
                                    allOnes = false;
                                }
                            }
                        }
                        if (allOnes) {
                            int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                            maxArea = Math.max(maxArea, area);
                        }
                    }
                }
            }
        }
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(rows³ × cols³)

We pick a top-left corner in O(rows × cols), a bottom-right corner in O(rows × cols), and then verify the rectangle in O(rows × cols). This gives O(rows² × cols² × rows × cols) = O(rows³ × cols³). For a 200×200 matrix, this is roughly 200⁶ ≈ 6.4 × 10¹³ operations — far too slow.

Space Complexity: O(1)

We use only a few integer variables. No additional data structures grow with input size.

Why This Approach Is Not Efficient

The brute force examines every possible rectangle and verifies each one cell by cell. With a 200×200 matrix, there are roughly O(n³ × m³) total operations (where n=rows, m=cols), which is approximately 6.4 × 10¹³ — far beyond what can be computed within time limits.

The core problem is that we are doing redundant work. When we check a rectangle and find it is all 1's, then extend it by one column, we re-scan the entire rectangle from scratch instead of leveraging the previous check. We also have no way to quickly skip over regions containing 0's.

Key insight: Instead of checking rectangles directly, we can precompute how many consecutive 1's extend to the left at each cell. Then for each cell we only need to scan upward while tracking the minimum width, which dramatically reduces the number of operations.

Better Approach - Dynamic Programming with Width Tracking

Intuition

Instead of checking every rectangle from scratch, we can precompute useful information. For each cell (i, j) that contains a '1', we compute the width of consecutive 1's ending at that cell in its row (looking leftward). We store this in a 2D array width[i][j].

Once we have the width at every cell, we can find rectangles efficiently: for any cell (i, j), we look upward through rows i, i-1, i-2, … while tracking the minimum width we have seen. At each row k above, the minimum width tells us how wide a rectangle can be that starts at row k and ends at row i. The height of that rectangle is i - k + 1, so the area is min_width × height.

Think of it like stacking bricks. At each cell, you know how many consecutive bricks stretch to the left. Then you look upward to see how tall of a wall you can build while the wall stays at least as wide as the narrowest row.

Step-by-Step Explanation

Let's trace through the matrix:

matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]

Step 1: Build the width table. For each cell with value '1', count consecutive 1's to the left (including itself). For '0' cells, width is 0.

width = [[1,0,1,0,0],
         [1,0,1,2,3],
         [1,2,3,4,5],
         [1,0,0,1,0]]

Step 2: For cell (2, 4), width = 5. Look upward:

  • Row 2: min_width = 5, height = 1, area = 5×1 = 5.
  • Row 1: width[1][4] = 3, min_width = min(5, 3) = 3, height = 2, area = 3×2 = 6.
  • Row 0: width[0][4] = 0, min_width = 0 → stop (width became 0).
  • Best area from this cell: 6.

Step 3: For cell (2, 3), width = 4. Look upward:

  • Row 2: min_width = 4, height = 1, area = 4.
  • Row 1: width[1][3] = 2, min_width = 2, height = 2, area = 4.
  • Row 0: width[0][3] = 0, min_width = 0 → stop.
  • Best area from this cell: 4.

Step 4: For cell (2, 2), width = 3. Look upward:

  • Row 2: min_width = 3, height = 1, area = 3.
  • Row 1: width[1][2] = 1, min_width = 1, height = 2, area = 2.
  • Row 0: width[0][2] = 1, min_width = 1, height = 3, area = 3.
  • Best area from this cell: 3.

Step 5: Continue for all cells. The maximum area found across all cells is 6 (from cell (2,4) looking up 2 rows with min width 3).

Result: 6.

DP Width Tracking — Building Width Table and Scanning Upward — Watch how we first compute widths of consecutive 1's for each cell, then for each cell scan upward while tracking the minimum width to find the largest rectangle.

Algorithm

  1. Create a 2D array width of the same size as the matrix, initialized to 0.
  2. For each cell (i, j):
    • If matrix[i][j] == '0', set width[i][j] = 0.
    • Otherwise, set width[i][j] = (j == 0) ? 1 : width[i][j-1] + 1.
  3. For each cell (i, j) where width[i][j] > 0:
    • Set min_width = width[i][j].
    • Scan upward from row i to row 0:
      • Update min_width = min(min_width, width[k][j]) at row k.
      • If min_width == 0, break (no valid rectangle can extend through this row).
      • Compute area = min_width × (i - k + 1) and update max_area.
  4. Return max_area.

Code

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) return 0;
        int cols = matrix[0].size();
        
        vector<vector<int>> width(rows, vector<int>(cols, 0));
        int maxArea = 0;
        
        // Build width table
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    width[i][j] = (j == 0) ? 1 : width[i][j-1] + 1;
                }
            }
        }
        
        // For each cell, scan upward
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (width[i][j] == 0) continue;
                int minWidth = width[i][j];
                for (int k = i; k >= 0; k--) {
                    minWidth = min(minWidth, width[k][j]);
                    if (minWidth == 0) break;
                    int area = minWidth * (i - k + 1);
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
};
class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        
        # Build width table
        width = [[0] * cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '1':
                    width[i][j] = 1 if j == 0 else width[i][j-1] + 1
        
        max_area = 0
        # For each cell, scan upward
        for i in range(rows):
            for j in range(cols):
                if width[i][j] == 0:
                    continue
                min_width = width[i][j]
                for k in range(i, -1, -1):
                    min_width = min(min_width, width[k][j])
                    if min_width == 0:
                        break
                    area = min_width * (i - k + 1)
                    max_area = max(max_area, area)
        return max_area
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        
        int[][] width = new int[rows][cols];
        int maxArea = 0;
        
        // Build width table
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    width[i][j] = (j == 0) ? 1 : width[i][j-1] + 1;
                }
            }
        }
        
        // For each cell, scan upward
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (width[i][j] == 0) continue;
                int minWidth = width[i][j];
                for (int k = i; k >= 0; k--) {
                    minWidth = Math.min(minWidth, width[k][j]);
                    if (minWidth == 0) break;
                    int area = minWidth * (i - k + 1);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(rows² × cols)

Building the width table takes O(rows × cols). For each of the rows × cols cells, the upward scan goes through at most rows iterations. So the scanning phase takes O(rows × cols × rows) = O(rows² × cols). Total: O(rows² × cols).

For a 200×200 matrix, this is roughly 200² × 200 = 8 × 10⁶ — comfortably within time limits.

Space Complexity: O(rows × cols)

We store the width table, a 2D array of the same size as the input matrix.

Why This Approach Is Not Efficient

While O(rows² × cols) is a massive improvement over the brute force, the upward scanning at each cell still has redundancy. For each column, we repeatedly scan upward through rows, and this per-cell upward scan is the bottleneck.

The key insight for further improvement: instead of scanning upward for each cell, we can reformulate the problem. If we treat each row as the base of a histogram — where the bar height at each column is the count of consecutive 1's above (including that row) — then the maximal rectangle ending at that row is the largest rectangle in a histogram. The largest rectangle in a histogram can be solved in O(cols) time using a monotonic stack. Running this for each row gives us O(rows × cols) total — a linear scan of the matrix.

Optimal Approach - Histogram with Monotonic Stack

Intuition

The optimal approach transforms the 2D matrix problem into a series of 1D histogram problems.

Imagine you are standing below the matrix and looking upward at each row. For each column, you count how many consecutive 1's are stacked above (including the current row). If you hit a 0, the stack resets to zero. This gives you a histogram of heights for that row.

For example, with our matrix:

Row 0: heights = [1, 0, 1, 0, 0]   (just the first row)
Row 1: heights = [2, 0, 2, 1, 1]   (row 0-1 stacked)
Row 2: heights = [3, 1, 3, 2, 2]   (row 0-2 stacked)
Row 3: heights = [4, 0, 0, 3, 0]   (row 0-3, resets where 0's appear)

For each row's histogram, the largest rectangle in that histogram corresponds to the largest all-1's rectangle in the original matrix that uses that row as its bottom edge. We find the largest rectangle in each histogram using a monotonic stack — a stack that keeps bar indices in order of increasing height.

The monotonic stack trick works because: for each bar, we need to find how far left and right it can extend while remaining the shortest bar in the range. The stack lets us find these boundaries in amortized O(1) per bar.

Four histograms showing how heights accumulate row by row from the binary matrix
Four histograms showing how heights accumulate row by row from the binary matrix

Step-by-Step Explanation

Let's trace through the full matrix:

matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]

Step 1: Initialize heights = [0, 0, 0, 0, 0].

Step 2: Process Row 0. Update heights:

  • Col 0: '1' → heights[0] = 0+1 = 1
  • Col 1: '0' → heights[1] = 0
  • Col 2: '1' → heights[2] = 0+1 = 1
  • Col 3: '0' → heights[3] = 0
  • Col 4: '0' → heights[4] = 0
  • heights = [1, 0, 1, 0, 0]
  • Largest rectangle in this histogram = 1. max_area = 1.

Step 3: Process Row 1. Update heights:

  • Col 0: '1' → heights[0] = 1+1 = 2
  • Col 1: '0' → heights[1] = 0
  • Col 2: '1' → heights[2] = 1+1 = 2
  • Col 3: '1' → heights[3] = 0+1 = 1
  • Col 4: '1' → heights[4] = 0+1 = 1
  • heights = [2, 0, 2, 1, 1]
  • Largest rectangle in histogram [2,0,2,1,1]: the best is width=3 at height=1 (indices 2-4), area = 3. max_area = 3.

Step 4: Process Row 2. Update heights:

  • Col 0: '1' → heights[0] = 2+1 = 3
  • Col 1: '1' → heights[1] = 0+1 = 1
  • Col 2: '1' → heights[2] = 2+1 = 3
  • Col 3: '1' → heights[3] = 1+1 = 2
  • Col 4: '1' → heights[4] = 1+1 = 2
  • heights = [3, 1, 3, 2, 2]
  • Largest rectangle in histogram [3,1,3,2,2]: Using the monotonic stack, we find the bar of height 2 can extend from column 2 to column 4, giving width=3, area=2×3=6. max_area = 6.

Step 5: Process Row 3. Update heights:

  • Col 0: '1' → heights[0] = 3+1 = 4
  • Col 1: '0' → heights[1] = 0
  • Col 2: '0' → heights[2] = 0
  • Col 3: '1' → heights[3] = 2+1 = 3
  • Col 4: '0' → heights[4] = 0
  • heights = [4, 0, 0, 3, 0]
  • Largest rectangle in histogram [4,0,0,3,0] = 4 (single bar at index 0). max_area stays 6.

Step 6: All rows processed. Return max_area = 6.

Now let's trace the monotonic stack for Row 2's histogram [3, 1, 3, 2, 2] in detail:

Stack trace for [3, 1, 3, 2, 2]:

  • i=0, h=3: Stack empty → push 0. Stack: [0].
  • i=1, h=1: heights[0]=3 ≥ 1 → pop 0. Width = 1 (stack empty, so width=i=1). Area = 3×1 = 3. Push 1. Stack: [1].
  • i=2, h=3: heights[1]=1 < 3 → push 2. Stack: [1, 2].
  • i=3, h=2: heights[2]=3 ≥ 2 → pop 2. Width = 3-1-1 = 1. Area = 3×1 = 3. Heights[1]=1 < 2 → push 3. Stack: [1, 3].
  • i=4, h=2: heights[3]=2 ≥ 2 → pop 3. Width = 4-1-1 = 2. Area = 2×2 = 4. Heights[1]=1 < 2 → push 4. Stack: [1, 4].
  • End: Pop 4. Width = 5-1-1 = 3. Area = 2×3 = 6. Pop 1. Width = 5. Area = 1×5 = 5.
  • Largest area for this histogram = 6.

Monotonic Stack — Largest Rectangle in Histogram [3,1,3,2,2] — Watch the monotonic stack process Row 2's histogram to find the largest rectangle area. The stack tracks bar indices in increasing height order, and pops when a shorter bar arrives.

Algorithm

  1. Initialize a heights array of size cols, all zeros.
  2. For each row i in the matrix:
    a. Update the heights array:
    • For each column j: if matrix[i][j] == '1', increment heights[j] by 1. Otherwise, reset heights[j] to 0.
      b. Compute the largest rectangle in the histogram defined by heights:
    • Use a monotonic stack to find, for each bar, the nearest shorter bar on the left and right.
    • For each bar at index j with height h: area = h × (right_boundary - left_boundary - 1).
    • Track the maximum area.
      c. Update the global max_area with this row's histogram result.
  3. Return max_area.

Code

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) return 0;
        int cols = matrix[0].size();
        
        vector<int> heights(cols, 0);
        int maxArea = 0;
        
        for (int i = 0; i < rows; i++) {
            // Update heights for current row
            for (int j = 0; j < cols; j++) {
                heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
            }
            // Find largest rectangle in this histogram
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> stk;
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            int currHeight = (i == n) ? 0 : heights[i];
            while (!stk.empty() && heights[stk.top()] >= currHeight) {
                int h = heights[stk.top()];
                stk.pop();
                int width = stk.empty() ? i : i - stk.top() - 1;
                maxArea = max(maxArea, h * width);
            }
            stk.push(i);
        }
        return maxArea;
    }
};
class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        cols = len(matrix[0])
        heights = [0] * cols
        max_area = 0
        
        for row in matrix:
            # Update heights for current row
            for j in range(cols):
                heights[j] = heights[j] + 1 if row[j] == '1' else 0
            
            # Find largest rectangle in this histogram
            max_area = max(max_area, self._largest_rectangle(heights))
        
        return max_area
    
    def _largest_rectangle(self, heights: list[int]) -> int:
        n = len(heights)
        stack = []
        max_area = 0
        
        for i in range(n + 1):
            curr_height = heights[i] if i < n else 0
            while stack and heights[stack[-1]] >= curr_height:
                h = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * width)
            stack.append(i)
        
        return max_area
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        
        int[] heights = new int[cols];
        int maxArea = 0;
        
        for (int i = 0; i < rows; i++) {
            // Update heights for current row
            for (int j = 0; j < cols; j++) {
                heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
            }
            // Find largest rectangle in this histogram
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            int currHeight = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] >= currHeight) {
                int h = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(rows × cols)

For each of the rows rows, we update the heights array in O(cols) and run the histogram algorithm in O(cols) (each bar is pushed and popped from the stack at most once). Total: rows × O(cols) = O(rows × cols).

For a 200×200 matrix, this is 40,000 operations — extremely fast.

Space Complexity: O(cols)

We maintain a heights array of size cols and a stack that holds at most cols elements. No 2D auxiliary structures are needed.