Maximal Square

LeetCode #85

Description:

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

Example:

Given a binary matrix, find the maximum size rectangle binary-sub-matrix with all 1’s.

Input :   0 1 1 0
          1 1 1 1
          1 1 1 1
          1 1 0 0

Output :  1 1 1 1
          1 1 1 1

Idea:

In this post an interesting method is discussed that uses largest rectangle under histogram as a subroutine. Below are steps. The idea is to update each column of a given row with corresponding column of previous row and find largest histogram area for for that row.

Step 1: Find maximum area for row[0]
Step 2:
    for each row in 1 to N - 1
        for each column in that row
            if A[row][column] == 1
              update A[row][column] with
                A[row][column] += A[row - 1][column]
    find area for that row
    and update maximum area so far 
Illustration :

step 1:    0 1 1 0  maximum area  = 2
step 2:
    row 1  1 2 2 1  area = 4, maximum area becomes 4
    row 2  2 3 3 2  area = 8, maximum area becomes 8
    row 3  3 4 0 0  area = 6, maximum area remains 8

Code:

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

        int m=matrix.size();
        int n=matrix[0].size();
        // This is just to convert the Char vector to Int vector
        vector<vector<int>> matrix_int(m, vector<int>(n));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                matrix_int[i][j]=matrix[i][j]-'0';
            }
        }

        int max_area=0;
        max_area = largestRectangleArea(matrix_int[0]);
        for(int i=1; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix_int[i][j]==1){
                    matrix_int[i][j] += matrix_int[i-1][j];
                }
            }
            max_area = max(max_area, largestRectangleArea(matrix_int[i]));
        }
        return max_area;
    }

    int largestRectangleArea(vector<int>& heights) {
        stack<int> s_height;

        int max_area=0;
        int i=0;
        while(i<heights.size()){
            if(s_height.empty()||heights[i]>heights[s_height.top()]){
                s_height.push(i++);
            }
            else{
                int indx=s_height.top();
                s_height.pop();
                int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
                max_area = max(curr_area, max_area);
            }
        }
        // Stack is not empty, keep pop and calculate
        while(!s_height.empty()){
            int indx=s_height.top();
            s_height.pop();
            int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
            max_area = max(curr_area, max_area);
        }
        return max_area;    
    }
};