Maximal Rectangle problem (using Monotonic queue)

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

The objective of this article is to solve the maximal rectangle problem using Monotonic queue. In this problem we are given a matrix consisting of only 0's and 1's, we need to find the largest rectangle consisting of only 1's and return its area.

Monotonic queue approach

In this method, we are going to construct a histogram and find the largest rectangle area that can be formed in the histogram for each row and compare these values to find the maximum rectangular area that can be formed in the given matrix.

How to construct a histogram?

We will use an array whose size is equal to the row size of the given matrix to construct a histogram and initialize it to 0. Traverse the matrix from top to bottom column. If the ith element of the row is 1 then we will add 1 to the ith element of the array and if it is zero then the ith element in the array will be zero. The value stored in the array represents the height of the bar and the width of the bar is 1.
Monotonic queue is used to find the maximum rectangular area in the given histogram.

Algorithm

Step 1: Traverse matrix from top to bottom column.
Step 2: Construct the histogram for each row.
Step 3: Find the maximum rectangular area possible in the given histogram.
Step 4: If the maximum rectangular area obtained is greater than the max area then the max area is equal to the area of the rectangle.
Step 5: Return the max area when the traversal gets completed.

Time and Space Complexity.

The no of operations to construct the histogram and finding the maximum rectangular area is O(row size). We repeat these steps for O(column size. Therefore, the time complexity is O(column size * row size).
The Space complexity is O(row size) because we are using an array whose size is equal to the row size of the given matrix to construct the histogram.

Example

Let the given matrix be [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]].Our objective is to find the
largest rectangle consisting of only 1's and return its area.

The matrix is:

Let us take an array to construct a histogram and initialize it to 0.

Array -> 0 0 0 0 0.

Now loop from top to bottom column.

Let us construct a histogram for the zeroth row.

The zeroth element is 1 in the zeroth row, Therefore add 1 to the zeroth element in the array.
The first element is 0 in the zeroth row, Therefore the first element in the array is 0.
The second element is 1 in the zeroth row, Therefore add 1 to the second element in the array.
The third element is 0 in the zeroth row, Therefore the third element in the array is 0.
The fourth element is 0 in the zeroth row, Therefore the fourth element in the array is 0.

Array -> 1 0 1 0 0.

The Largest rectangular area for this histogram is 1.

Let us construct a histogram for the first row.
The zeroth element is 1 in the first row, Therefore add 1 to the zeroth element in the array.
The first element is 0 in the first row, Therefore the first element in the array is 0.
The second element is 1 in the first row, Therefore add 1 to the second element in the array.
The third element is 1 in the first row, Therefore add 1 to the third element in the array.
The fourth element is 1 in the first row, Therefore add 1 to the fourth element in the array.

Array -> 2 0 2 1 1

The Largest rectangular area for this histogram is 3.

Let us construct a histogram for the second row.
The zeroth element is 1 in the second row, Therefore add 1 to the zeroth element in the array.
The first element is 1 in the second row, Therefore add 1 to the first element in the array.
The second element is 1 in the second row, Therefore add 1 to the second element in the array.
The third element is 1 in the second row, Therefore add 1 to the third element in the array.
The fourth element is 1 in the second row, Therefore add 1 to the fourth element in the array.

Array -> 3 1 3 2 2

The Largest rectangular area for this histogram is 6.

Let us construct a histogram for the third row.

The zeroth element is 1 in the third row, Therefore add 1 to the zeroth element in the array.
The first element is 0 in the third row, Therefore the first element in the array is 0.
The second element is 0 in the third row, Therefore the second element in the array is 0.
The third element is 1 in the third row, Therefore add 1 to the third element in the array.
The fourth element is 0 in the third row, Therefore the fourth element in the array is 0.

Array -> 4 0 0 3 0.

The Largest rectangular area for this histogram is 4.

Out of all these rectangular areas, the one with the maximum area is 6.

The solution to this problem is 6.

Implementing the Monotonic queue approach.

C++


#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;


//structure of montonic queue.
class MonotonicQueue {


     int monotonic_queue[10000];//array to store data.
     int index[10000];//stores the index of element in the given array
     int top=-1;//pointer which points to top of the array.


public:


/* add element n to the end of the line and returns how many days the element needs to
wait until warmer day.*/
int push(int n,int ind){
    while(top!=-1 && n<=monotonic_queue[top]){
           pop();
      }
      monotonic_queue[++top]=n;
      index[top]=ind;
    if(top==0){  // if element was empty before inserting the current item.
         return -1;
     }else{
         return index[top-1];
   }
}


// returns the min value in the current queue
   int peek(){
        return monotonic_queue[top];
    }


// remove the top element.
int pop(){
        return monotonic_queue[top--];
   }
};


/*function that returns an array where the data stored is the index of 
first smaller element present to the right of item.*/
vector<int> next_smaller_element_to_right (vector<int> T) {
        MonotonicQueue a;
        vector<int> ind;
        for(int i=T.size()-1;i>=0;i--){
            int x;
            if((x=a.push(T[i],i))==-1){
                ind.push_back(T.size()-1);
            }else{
            ind.push_back(x-1);
            }
        }
        reverse(ind.begin(),ind.end());
        return ind;
    }


/*function that returns an array where the data stored is the index of 
first smaller element present to the left of the item.*/
vector<int> next_smaller_element_to_left(vector<int> T) {
        MonotonicQueue b;
        vector<int> ind;
        for(int i=0;i<T.size();i++){
            int x;
            if((x=b.push(T[i],i))==-1){
                ind.push_back(0);
            }else{
            ind.push_back(b.push(T[i],i)+1);
            }
        }
        return ind;
    }
 

 //function that finds the maximum rectangular of the histogram .
 int largestRectangleArea(vector<int>& heights) {
 vector<int>min_right_ind=next_smaller_element_to_right(heights);
vector<int>min_left_ind=next_smaller_element_to_left(heights);
    int max=0;
    for(int i=0;i<heights.size();i++){
        int temp;
          temp=(min_right_ind[i]-min_left_ind[i]+1)*heights[i];
        if(temp>max){
            max=temp;
        }
    }
    return max;
    }


//function that returns the solution of the problem.
int maximalRectangle(vector<vector<int>>& matrix) 
{
        int x;
        if(matrix.size()!=0){
         x=matrix[0].size();
        }
        vector<int> array_to_construct_histogram(x,0);//initializing the vector with 0
        int maxarea=0;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                if(matrix[i][j]==1){
                    array_to_construct_histogram.at(j)+=1;
                }else if(matrix[i][j]==0){
                    array_to_construct_histogram.at(j)=0;
                }
            }
           int area=largestRectangleArea(array_to_construct_histogram);
            if(area>maxarea){
                maxarea=area;
            }   
        }
        return maxarea;
    }
   
 
    int main(){
    vector<vector<int>> T {
        {1,0,1,0,0},
        {1,0,1,1,1},
        {1,1,1,1,1},
        {1,0,0,1,0}
    };
    int solution=maximalRectangle(T);
    cout<<"The maximal rectangular area is "<<solution;
    }

Output

The maximal rectangular area is 6.

With this article at OPENGENUS, you must have the complete idea of solving Maximal Rectangle problem using Monotonic queue.