CHEFRECT-Editorial

CHEFRECT

Author: aniket_111
Tester: sahoomirnalin
Editorialist: aniket_111

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() {
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;
}``````