Skip to main content

Maximal Rectangle

Problem Statement:​

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

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 maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

Constraints:

  • Example:

✅ Solution: Monotonic Stack + Histogram Technique — Maximal Rectangle​

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;
        stack<int> st;
        int n = heights.size();

        for (int i = 0; i <= n; i++) {
            while (!st.empty() && (i == n || heights[st.top()] >= (i == n ? 0 : heights[i]))) {
                int height = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        return maxArea;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;

        int row = matrix.size();
        int col = matrix[0].size();
        vector<int> heights(col, 0);
        int maxArea = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // Update histogram heights
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            maxArea = max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }
};

📝 How It Works​

  • Problem Goal: Find the largest rectangle containing only 1s in a binary matrix.
  • Approach:
    • Treat each row as the base of a histogram.
    • Build cumulative heights as we move down row by row.
    • Apply the Largest Rectangle in Histogram algorithm on each row.
  • Step-by-Step:
    1. Initialize a height array with 0s.
    2. For each row:
      • If cell is '1', increment the height at that column.
      • If cell is '0', reset height to 0.
    3. Apply largestRectangleArea() on updated heights after each row.

🧩 Key Formula​

  • For each row, use:

    maxArea = max(maxArea, largestRectangleArea(heights));

  • Histogram heights:

    heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0

⏱️ Time & Space Complexity​

ApproachTime ComplexitySpace Complexity
Histogram + Monotonic StackO(N × M)O(M)
  • Where N = number of rows, M = number of columns.

⚠️ Edge Cases​

  • Empty matrix → Should return 0.
  • All zeros → Max area = 0.
  • All ones → Max area = row × col.

💡 Other Approaches​

  • DP Table Approach: Pre-calculate left/right boundaries per row.

    Similar time complexity but requires more memory management.

  • Brute Force: Check all possible rectangles.

    Time: O(N² × M²) — not practical for large matrices.

🔁 Related Problems​

  • LeetCode 85: Maximal Rectangle (Exact Problem)
  • LeetCode 84: Largest Rectangle in Histogram
  • LeetCode 221: Maximal Square

🛠️ Other Notes​

  • ✅ Real-world analogy:

    Imagine placing books in stacks row by row, and wanting the largest contiguous block of books.

  • ✅ Histogram-based row-by-row stacking is often used for similar matrix-based maximum area problems.

  • ✅ Always handle empty matrix cases before proceeding with core logic.

💬

Discussion & Doubts