# PROBLEM LINK:

* Author:* aniket_111

*sahoomirnalin*

**Tester:***aniket_111*

**Editorialist:**# DIFFICULTY:

HARD

# PREREQUISITES:

Basic mathematics, matrix, array.

# PROBLEM:

For a table in a restaurant which divided by n x m cells, the waiter has randomly placed Ice-cream and gulab jamun on each cell of the table. Find out the largest rectangle which can be formed by Ice-creams only such that there is no gulab jamun within the rectangle. Note: Ice-cream is represented by char values as ‘1’ and gulab jamun by ‘0’. The input is given in the form of n x m Matrix containing zeros and ones.

# EXPLANATION

Instead of forming every rectangle, then checking validity of rectangle, we can optimize the brute-force by only considering valid rectangles. For this, we can start from every cell and consider valid rectangle starting from that cell.

- Let the current cell be at
`(i, j)`

. - We first consider
`i`

th row and find maximum column length of 1s starting from`M[i][j]`

. - Then move to
`i+1`

th row and find maximum column length of 1s starting from`M[i+1][j]`

. Take minimum of all lengths and find the area and keep updating max area. - Continue similar process till you reach last row and then repeat the process for all other cells as well.
- Finally return maximum area found from all valid rectangles.

# TIME COMPLEXITY

Time complexity is O((mn)^2)

# SOLUTIONS:

```
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int maximalRectangle(vector<vector<char>>& M) {
if(!size(M)) return 0;
int ans = 0, m = size(M), n = size(M[0]);
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
for(int row = i, colLen = n, col; row < m && M[row][j] == '1'; row++) {
for(col = j; col < n && M[row][col] == '1'; col++);
colLen = min(colLen, col-j);
ans = max(ans, (row-i+1) * colLen);
}
return ans;
}
int main() {
// your code goes here
int n,m,ans=0;
char val;
vector<vector<char>> v2;
vector<char> v1;
cin>>n>>m;
for(int i=0;i<n;i++){
v1={};
for(int j=0;j<m;j++){
cin>>val;
v1.push_back(val);
}
v2.push_back(v1);
}
ans=maximalRectangle(v2);
cout << ans <<endl;
return 0;
}
```