13. Maximal Rectangle

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 = []
Output: 0


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


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


Example 5:
Input: matrix = [["0","0"]]
Output: 0

Solution: (Using Stack)

Approach: Same as Largest Rectangle in a Histogram Problem Computing largest rectangle in each row

class Solution
{
public:
    int maximalRectangle(vector<vector<char>> &matrix)
    {

        int n = matrix.size();
        if(n == 0){
            return 0;
        }
        int m = matrix[0].size();

        vector<vector<int>> v(n + 1, vector<int>(m, 0));

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < m; j++)
            {

                if (matrix[i - 1][j] == '1')
                {
                    v[i][j] = 1 + v[i - 1][j];
                }
                else
                {
                    v[i][j] = 0;
                }
            }
        }

        int maxArea = INT_MIN;

        for (int i = 1; i <= n; i++)
        {
            stack<int> ls;
            stack<int> rs;
            vector<int> lm(m);
            vector<int> rm(m);

            // Left Limit
            for (int j = 0; j < m; j++)
            {

                if (ls.empty())
                {
                    lm[j] = 0;
                    ls.push(j);
                }
                else if (!ls.empty() && v[i][ls.top()] < v[i][j])
                {
                    lm[j] = ls.top() + 1;
                    ls.push(j);
                }
                else
                {
                    while (!ls.empty() && v[i][ls.top()] >= v[i][j])
                    {
                        ls.pop();
                    }

                    if (ls.empty())
                    {
                        lm[j] = 0;
                    }
                    else
                    {
                        lm[j] = ls.top() + 1;
                    }
                    ls.push(j);
                }
            }

            // Right Limit
            for (int j = m - 1; j >= 0; j--)
            {

                if (rs.empty())
                {
                    rm[j] = m - 1;
                    rs.push(j);
                }
                else if (!rs.empty() && v[i][rs.top()] < v[i][j])
                {
                    rm[j] = rs.top() - 1;
                    rs.push(j);
                }
                else
                {
                    while (!rs.empty() && v[i][rs.top()] >= v[i][j])
                    {
                        rs.pop();
                    }

                    if (rs.empty())
                    {
                        rm[j] = m - 1;
                    }
                    else
                    {
                        rm[j] = rs.top() - 1;
                    }
                    rs.push(j);
                }
            }

            for (int k = 0; k < rm.size(); k++)
            {
                int area = (rm[k] - lm[k] + 1) * v[i][k];
                if (area > maxArea)
                {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
};

Time Complexity: O(n * m) Space Compexity: O(n + m)