Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximum Size Rectangle Sub-matrix With All 1's

Hard
0/120
Average time to solve is 10m
profile
Contributed by
94 upvotes
Asked in companies
AmazonGoogleApple

Problem statement

You are given an 'N' * 'M' sized binary-valued matrix 'MAT, where 'N' is the number of rows and 'M' is the number of columns. You need to return the maximum size (area) of the submatrix which consists of all 1’s i.e. the maximum area of a submatrix in which each cell has only the value ‘1’.

subMatrix_image

In the above image, areas in green, red, and violet color are all submatrices of the original 4x4 matrix.

Note:

1. Binary valued matrix has only two values in each cell : 0 and 1.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.
3. The area of a matrix with 'h' rows and 'w' columns is equal to 'h' * 'w'. 
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two space-separated integers 'N' and 'M', where 'N' = the number of rows in the given matrix and 'M' = the number of columns in the given matrix.

Then 'N' lines follow for each test case. Each line contains 'M' space-separated integers (either 1 or 0) denoting matrix elements.
Output Format:
For each test case print in a single line the area of maximum size submatrix of all 1’s in the given matrix on a new line.

The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'T' <= 50
1 <= 'N', 'M' <= 100

Time Limit: 1 sec
Sample Input 1:
2
2 2
1 1
1 1
5 4
1 0 1 1
1 0 1 1
0 1 0 1
1 1 1 1
0 0 0 1
Sample Output 1:
4
5
Explanation For Sample Input 1:
For First Test Case: It is easy to see that whole matrix of size 2 * 2 contains '1' only hence the required area will be 4.

For Second Test Case:

explanationSampleInput1

Sample Input 2:
2
2 2
1 0
0 1
4 4
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
Sample Output 2:
1
8
Hint

Can you precalculate the overlapping subproblems? 

Approaches (2)
Dynamic Programming.
  1. We start from the first row and move downwards.
  2. We create three 1-dimensional arrays HEIGHT[], LEFT[], RIGHT[].
  3. ‘HEIGHT’[i]: stores the number of current continuous 1’s in column i.
  4. LEFT[i] : stores the leftmost index ‘j’ such that all indices say ‘K’, ‘K’ belongs to [j, i], ‘HEIGHT’[k] >= ‘HEIGHT’[i].
  5. RIGHT [i]: stores the rightmost index ‘j’ such that all indices say ‘K’, ‘K’ belongs to [i, j], ‘HEIGHT’[k] >= ‘HEIGHT’[i].
  6. By the above definitions, it’s easier to figure out that we can update our maximum area with the value (‘HEIGHT’[i] * (RIGHT [i] - LEFT [i])).
  7. Now let’s think how will we update the above three 1-dimensional arrays itself.
  8. Initialize the ‘HEIGHT’[] array with 0.
  9. Iterate through the rows from 0 to N-1.
  10. For each column:
  11. If the current value (MAT [i][j]) is 1, then update ‘HEIGHT’[j]++.
  12. Else reset the value of ‘HEIGHT’[j] to 0.
  13. Note that:
  14. Initially, ‘HEIGHT’ was initialized to 0. So LEFT[] array should be initialised to 0 as per definition.
  15. And similarly, RIGHT[] array should be initialized to M.
  16. Updating the LEFT[] array in each iteration among rows 0 to N-1:
  17. We scan from left to right.
  18. Initialize LEFTBOUNDARY = 0, which means left boundary for all 1’s in the current row.
  19. Iterate in the current row:
  20. If the current value  (MAT [i][j]) is 1, then you can reset the LEFT[j] from 0 to LEFTBOUNDARY.
  21. Else left[j] = 0 and update LEFTBOUNDARY to j+1. As the current value is 0, so next LEFTBOUNDARY for all the cells in the Matrix ahead of column j is at least j+1.
  22. Similarly, for the RIGHT[] array  in each iteration among rows 0 to N-1:
  23. We scan from right to left.
  24. Initialize RIGHTBOUNDARY = 0, which means right boundary for all 1’s in the current row.
  25. Iterate in the current row:
  26. If the current value  (MAT[i][j]) is 1, then you can reset the RIGHT[j] from M to RIGHTBOUNDARY.
  27. Else RIGHT[j] = 0 and update RIGHTBOUNDARY to j-1. As current value is 0, so next RIGHTBOUNDARY for all the cells in the Matrix before column j is atmost j-1.

 

Time Complexity

O(N*M), where 'N' is the number of rows and ‘M’ is the number of columns in the matrix.

 

As we are traversing the whole matrix of size N * M it will require an N * M steps hence the overall complexity will be O(N*M). 

Space Complexity

O(M), where 'M' is the number of columns in the matrix.

 

As we are storing LEFT and RIGHT arrays of size ‘M’ it will take O(M) space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Maximum Size Rectangle Sub-matrix With All 1's
All tags
Sort by
Search icon

Interview problems

easy solution using stack and histogram

#include <stack>

 

 vector<int> nextSmallerElement(vector<int> arr, int n)

{

    stack<int> s;

    vector<int> ans(n);

 

    s.push(-1);

 

    for(int i = n-1; i >= 0; i--){

        int curr = arr[i];

        while(s.top() != -1 && arr[s.top()] >= curr ){

            s.pop();

        }

        ans[i] = s.top();

        s.push(i);

    }

 

    return ans;

}

 

    vector<int> prevSmallerElement(vector<int> arr, int n)

{

    stack<int> s;

    vector<int> ans(n);

 

    s.push(-1);

 

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

        int curr = arr[i];

        while(s.top() != -1 && arr[s.top()] >= curr ){

            s.pop();

        }

        ans[i] = s.top();

        s.push(i);

    }

 

    return ans;

}

 

    int largestRectangleArea(vector<int>& heights, int n) {

        

 

        vector<int> next(n);

        next = nextSmallerElement(heights, n);

 

        vector<int> prev(n);

        prev = prevSmallerElement(heights, n);

        int area = 0;

 

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

            int length = heights[i];

            

            if(next[i] == -1){

                next[i] = n;

            }

            int breadth = (next[i] - prev[i] - 1);

            int new_area = length * breadth;

            area = max(new_area, area);

        }

        return area;

    }

    

 

    int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &M, int n, int m) {

        int area = largestRectangleArea(M[0], m);

        

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

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

                if(M[i][j] != 0)

                    M[i][j] += M[i-1][j];

                else

                    M[i][j] = 0;

            }

        }

        

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

            area = max(largestRectangleArea(M[i], m), area);

        }

        

        return area;

    }

    

262 views
0 replies
0 upvotes

Interview problems

C++ || Easy To Understand

#include <vector>

#include <stack>

#include <iostream>

 

using namespace std;

 

int largestRectangleArea(const vector<int>& heights) {

    int n = heights.size();

    stack<int> s;

    int maxArea = 0;

 

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

        while (!s.empty() && (i == n || heights[i] < heights[s.top()])) {

            int height = heights[s.top()];

            s.pop();

            int width = s.empty() ? i : i - s.top() - 1;

            maxArea = max(maxArea, height * width);

        }

        s.push(i);

    }

 

    return maxArea;

}

 

int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &matrix, int rows, int cols) {

    if (matrix.empty() || matrix[0].empty()) {

        return 0;

    }

 

    vector<int> heights(cols, 0);

    int maxArea = 0;

 

    for (int i = 0; i < rows; ++i) {

        for (int j = 0; j < cols; ++j) {

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

        }

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

    }

 

    return maxArea;

}

 

390 views
0 replies
0 upvotes

Interview problems

python

from sys import stdin, stdout, setrecursionlimit

 

def nextsmaller(arr):

n=len(arr)

stack=[]

ans=[-1]*n

for i in range(len(arr)):

while stack and arr[stack[-1]] >= arr[i]:

stack.pop()

if not stack:

ans[i]=-1

else:

 

ans[i]=stack[-1]

stack.append(i)

return ans

def prevsmaller(arr):

stack=[]

n=len(arr)

ans=[-1]*n

 

for i in range(n-1,-1,-1):

while stack and arr[stack[-1]] >= arr[i]:

stack.pop()

if not stack:

ans[i]=-1

else:

 

ans[i]=stack[-1]

stack.append(i)

return ans

def findMaxwidth(arr):

next_smaller_arr=nextsmaller(arr)

prev_smaller_arr=prevsmaller(arr)

maxA=0

n=len(arr)

for i in range(len(arr)):

if prev_smaller_arr[i]==-1:

prev_smaller_arr[i]=n

rectangle_area=(prev_smaller_arr[i]-next_smaller_arr[i]-1)*arr[i]

maxA=max(maxA,rectangle_area)

return maxA

def maximalAreaOfSubMatrix(mat,n,m):

height=[0]*m

maxArea=0

for i in range(n):

for j in range(m):

if mat[i][j]==1:

height[j]+=1

else:

height[j]=0

area=findMaxwidth(height)

maxArea=max(area,maxArea)

return maxArea

 

 

57 views
0 replies
0 upvotes

Interview problems

cpp using MAHistogram

#include<bits/stdc++.h>

 

int largestRectangleArea(vector<int>& heights) {

        // find leftSmallest

        // find righSmallest

        // use formula maxA = max(maxA, heights[i] * (rightSmall[i] - leftSmall[i] + 1));

        int n = heights.size();

        stack<int> st;

        int leftSmall[n];

        int rightSmall[n];

        

 

        // lets find the leftSmaller which will be used as a boundary for us

        // the codes are almost similar for leftSaller and rightSmaller

 

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

 

            while(!st.empty()&&heights[i]<=heights[st.top()]){

              st.pop();

            }

 

            if(st.empty())leftSmall[i]=0;

            else leftSmall[i]=st.top()+1;

 

            st.push(i);

        }

 

        // Empty the stack as we will use it again for rightSmaller element

        // It is better to pop() all the elements once you are done working with it

        while (!st.empty()) {

            st.pop();

        }

        // Now we have to find rightSmaller

        for (int i = n - 1; i >= 0; i--) {

            while (!st.empty() && heights[st.top()] >= heights[i]) {

                st.pop();

            }

 

            if (st.empty()) rightSmall[i] = n - 1;

            else  rightSmall[i] = st.top() - 1;

            st.push(i);

        }

 

        int maxA = 0;

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

            maxA = max(maxA, heights[i] * (rightSmall[i] - leftSmall[i] + 1));

        }

 

        return maxA;

    }

int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &matrix, int n, int m){

    // Write your code here.

    vector<int>heights2(m,0);

      int maxi=0;

 

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

        vector<int>heights;

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

          if(matrix[i][j]==1)heights.push_back(1+heights2[j]);

            else heights.push_back(0);

          }

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

        heights2=heights;

      }

      return maxi;

}

125 views
0 replies
0 upvotes

Interview problems

Java Solution using the concept of Max Rectangle of Histogram

import java.util.Stack;
public class Solution {
    public static int maxAreaHistogram(int heights[]){
        int n=heights.length,maxArea=0;
        Stack<Integer> st=new Stack<>();
        for(int i=0;i<=n;i++){
            while(!st.isEmpty() && (i==n || heights[st.peek()]>=heights[i])){
              int h=heights[st.pop()];
              int w=i;
              if(!st.isEmpty()) w=i-st.peek()-1;
              maxArea=Math.max(maxArea,h*w);
            }
            st.push(i);
        }
        return maxArea;
    }
	public static int maximalAreaOfSubMatrixOfAll1(int[][] mat, int n, int m) {
		// Write your code here.
        int heights[]=new int[m],maxArea=0;
        for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
            if(mat[i][j]==1) heights[j]++;
            else heights[j]=0;
          }
          int currArea= maxAreaHistogram(heights);
          maxArea=Math.max(currArea,maxArea);
        }
        return maxArea;
	}
}
172 views
0 replies
0 upvotes

Interview problems

C++ Solution || Using Stack

#include <stack>

vector<int> nextSmallerElement(vector<int> &arr, int n)

{

    stack<int> s;

    s.push(-1);

    vector<int> ans(n);

    for(int i=n-1;i>=0;i--){

        int curr=arr[i];

        while(s.top() !=-1 && arr[s.top()]>=curr){

            s.pop();

        }

        ans[i]=s.top();

        s.push(i);

    }

    return ans;

}

vector<int> prevSmallerElement(vector<int> &arr, int n)

{

    stack<int> s;

    s.push(-1);

    vector<int> ans(n);

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

        int curr=arr[i];

        while(s.top() !=-1 && arr[s.top()]>=curr){

            s.pop();

        }

        ans[i]=s.top();

        s.push(i);

    }

    return ans;

}

 int largestRectangle(vector < int > & heights,int n) {

   vector<int>next(n);

   next=nextSmallerElement(heights,n);

 

   vector<int>prev(n);

   prev=prevSmallerElement(heights,n);

 

   int area=-1;

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

     int l=heights[i];

     if(next[i]==-1){

       next[i]=n;

     }

     int b=next[i]-prev[i]-1;

     int newArea=l*b;

     area=max(area,newArea);

   }

   return area;

 }

int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &mat, int n, int m){

    int area=largestRectangle(mat[0],m);

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

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

                if(mat[i][j]!=0){

                    mat[i][j]=mat[i][j] + mat[i-1][j];

                }

                else{

                    mat[i][j]=0;

                }

            }

            int newArea=largestRectangle(mat[i],m);

            area=max(area,newArea);

        }

        return area;

}

181 views
0 replies
1 upvote

Interview problems

[C++]✅Easy Solution | Monotonic Stack | Maximum Size Rectangle Sub-matrix With All 1's

#include<bits/stdc++.h>

vector<int> nextSmaller(vector<int> &arr, int n){
	vector<int>ans(n);
	stack<int>st;
	st.push(-1);
	for(int i=n-1; i>=0; i--){
		int curr = arr[i];
		while(st.top() != -1 && arr[st.top()] >= curr){
			st.pop();
		}
		ans[i] = st.top();
		st.push(i);
	}
	return ans;
}

vector<int> prevSmaller(vector<int> &arr, int n){
	vector<int>ans(n);
	stack<int>st;
	st.push(-1);
	for(int i=0; i<n; i++){
		int curr = arr[i];
		while(st.top() != -1 && arr[st.top()] >= curr){
			st.pop();
		}
		ans[i] = st.top();
		st.push(i);
	}
	return ans;
}

int largestArea(vector<int>& heights) {
	int area = INT_MIN, n = heights.size();
	vector<int>next = nextSmaller(heights, n);
	vector<int>prev = prevSmaller(heights, n);

	for(int i=0; i<n; i++){
		int l = heights[i];
		if(next[i]==-1) next[i] = n;
		int b = next[i] - prev[i] - 1;

		int newArea = l*b;
		area = max(area, newArea);
	}
	return area;
}

int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &matrix, int n, int m){
	int maxArea = INT_MIN;
	vector<int>histogram(m, 0);
	for(int i=0; i<matrix.size(); i++){
		for(int j=0; j<histogram.size(); j++){
			if(matrix[i][j]== 1) histogram[j]++;
			else histogram[j] = 0;
		}
		maxArea = max(maxArea, largestArea(histogram));
	}
	return maxArea;
}
93 views
0 replies
1 upvote

Interview problems

Easy c++ solution

#include <bits/stdc++.h>

 

vector<int> nextRectangle(vector<int> heights, int n){

 

    vector<int> ans(n);

    stack<int> s;

    s.push(-1);

 

    for(int i=n-1; i>=0; i--){

 

        int curr = heights[i];

 

        while(s.top() != -1 && heights[s.top()] >= curr){

            s.pop();

        }

 

        ans[i] = s.top();

        s.push(i);

 

    }

 

    return ans;

 

}

 

vector<int> prevRectangle(vector<int> heights, int n){

 

    vector<int> ans(n);

    stack<int> s;

    s.push(-1);

 

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

 

        int curr = heights[i];

 

        while(s.top() != -1 && heights[s.top()] >= curr){

            s.pop();

        }

 

        ans[i] = s.top();

        s.push(i);

 

    }

 

    return ans;

 

}

 

int largestArea(vector<int> heights, int n){

 

    int area = INT_MIN;

 

    vector<int> next(n);

    next = nextRectangle(heights, n);

 

    vector<int> prev(n);

    prev = prevRectangle(heights, n);

 

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

 

        int l = heights[i];

 

        if(next[i] == -1){

            next[i] = n;

        }

 

        int w = next[i] - prev[i] - 1;

 

        int newArea = l * w;

 

        area = max(area, newArea);

 

    }

 

    return area;

 

}

 

int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &mat, int n, int m){

 

    int area = largestArea(mat[0], m);

 

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

        

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

 

            // Row update : by adding prev row's value

            if(mat[i][j] != 0)

                mat[i][j] = mat[i][j] + mat[i-1][j];

            else

                mat[i][j] = 0;

 

        }

 

        area = max(area, largestArea(mat[i], m));

    }

 

    return area;

 

}

57 views
0 replies
1 upvote

Interview problems

C++ Solution || Aditya Verma Approach


Simply convert 2D matrix -> 1D matrix and apply Max Area in Histogram concept(MAH)
MAH = (nsr-nsl-1)*height;
nsl : next smaller to left
nsr : next smaller to right




#include <bits/stdc++.h>

vector<int> nsr(vector<int>arr, int n){

    stack<pair<int,int>> s;

    vector<int>ans;

    for(int i=n-1; i>=0; i--){

        if(s.empty()) ans.push_back(n);

        else if(!s.empty() && s.top().first<arr[i])

            ans.push_back(s.top().second);

        else {

            while(!s.empty() && s.top().first>=arr[i])

              s.pop();

            if(s.empty()) ans.push_back(n);

            else ans.push_back(s.top().second);  

        }

        s.push({arr[i],i});

    }

    reverse(ans.begin(),ans.end());

    return ans;

}


vector<int> nsl(vector<int>arr, int n){

    stack<pair<int,int>> s;

    vector<int>ans;

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

       if(s.empty()) ans.push_back(-1);

        else {

            while(!s.empty() && s.top().first>=arr[i])

              s.pop();

            if(s.empty()) ans.push_back(-1);

            else ans.push_back(s.top().second);  

        }

        s.push({arr[i],i});

    }

    return ans;

}



int MAH(vector<int> heights, int n) {

        vector<int>nsr1(n);

        nsr1 = nsr(heights,n);

        vector<int>nsl1(n);

        nsl1 = nsl(heights, n);

        int area = INT_MIN;

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

            int width = nsr1[i]-nsl1[i]-1;  //width=n-p-1

            area = max(area, heights[i]*width);

        }

        return area;

    }



int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &mat, int n, int m){

        vector<int> v;

        for(int j=0;j<m;j++)

          v.push_back(mat[0][j]);



        int mx = MAH(v, m);

        

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

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

                if(mat[i][j]!=0)

                    v[j] = v[j]+mat[i][j];
                else  v[j]=0;

            }

            mx = max(mx, MAH(v, m));

        }

        return mx;

}
67 views
0 replies
0 upvotes

Interview problems

Check This

#include <bits/stdc++.h>

vector<int> nextSmaller(vector<int>arr, int n)

{

    stack<int> s;

    s.push(-1);

    

    vector<int>ans(n);

    for(int i=n-1; i>=0; i--){

        int cur=arr[i];

        while(s.top() !=-1 && arr[s.top()]>= cur){

            s.pop();

        }

        ans[i]=s.top();

        s.push(i);

    }

    return ans;

}

vector<int> prevSmaller(vector<int>arr, int n){

    stack<int> s;

    s.push(-1);

    

    vector<int>ans(n);

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

        int cur=arr[i];

        while(s.top() !=-1 && arr[s.top()]>= cur){

            s.pop();

        }

        ans[i]=s.top();

        s.push(i);

    }

    return ans;

}

int largestRectangleArea(vector<int> heights, int n) {

        //int n=heights.size();

        vector<int>next(n);

        next = nextSmaller(heights,n);//for storing index of next smaller

 

        vector<int>prev(n);

        prev = prevSmaller(heights, n);//for storing index of pre smaller index

        int area = INT_MIN;

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

            //calculate area

            int l = heights[i];

            

            //one case when all the elements are same like [2,2,2,2] then

            //next will be [-1,-1,-1,-1] =prev which will give width =-1

            if(next[i]==-1){

                next[i]=n;

            }

            int b = next[i]-prev[i]-1;  //b=n-p-1

            int newArea = l*b;

            area = max(area, newArea);

 

        }

        return area;

    }

int maximalAreaOfSubMatrixOfAll1(vector<vector<int>> &mat, int n, int m){

     //for first row

        int area = largestRectangleArea(mat[0], m);

        //move to next rows 

        //remaining rows

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

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

                //update row by adding prev row values

                if(mat[i][j]!=0)//is base row has zero then keep it zero

                {

                    mat[i][j] = mat[i][j]+ mat[i-1][j]; //M[i-1][j] is prev row

                }

                else{

                    mat[i][j]=0;

                }

                //entire row is now update

                //now compute ara

            }

            int newArea = largestRectangleArea(mat[i], m);

            area = max(area, newArea);

        }

        return area;

}

58 views
0 replies
1 upvote
Full screen
Console