DSA

Maximal Rectangle

Dynamic Programming. Time O(m * n), Space O(n).

August 8, 2026

DSA Dynamic Programming DP LeetCode Practice

Practice Link

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.

We reduce this to repeated calls of "Max Rectangle in Histogram". For each row i, we build a histogram where heights[j] is the number of consecutive 1s ending at row i in column j (reset to 0 if the cell is 0). We then run the O(n) stack-based histogram algorithm on that row's heights and update the global maximum area. This processes all m rows, each in O(n), giving O(m*n) overall time with only O(n) space for the heights array and the stack.

cpp

class Solution {
public:
    int maxAreaInHistogram(vector<int>& heights)
    {
        stack<int> stk;
        int maxArea=0;

        for(int i=0;i<=heights.size();i++)
        {
            while(!stk.empty() && (i==heights.size() || heights[stk.top()] >= heights[i]))
            {
                int height = heights[stk.top()];
                stk.pop();

                int width = 0;
                if(stk.empty())
                    width= i;
                else
                    width = i - stk.top() -1;

                maxArea = max(maxArea, height*width);
            }

            stk.push(i);
        }
        return maxArea;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> heights(n, 0);
        int maxArea=0;

        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='1')
                    heights[j]++;
                else
                    heights[j]=0;
            }
            int area = maxAreaInHistogram(heights);
            maxArea = max(maxArea, area);
        }
        return maxArea;
    }
};

Time Complexity: O(m * n)

Space Complexity: O(n)

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).

Related articles