you are given a matrix with 0 and 1's. you have to find the largest rectangle in the matrix such that you can swap columns

with any other column.

Ex- 0 1 0 1 0

0 1 0 1 1

1 1 0 1 0

the largest rectangle's area is 6 in this case because we can swap column 2 with column 3 so

the matrix after swapping will be

0 0 1 1 0

0 0 1 1 1

1 0 1 1 0

to store them

so for this the values in array will be

0 1 0 1 0

0 2 0 2 1

1 3 0 3 0

so the mechanism of filling the array will

ar[i][j] = ar[i-1][j]+1 if i>0 && a[i][j]==1

= 1 if i==0 && a[i][j]=1

= 0 else

step 2 - we will sort the rows in decreasing fashion

so after sorting step the matrix will be

1 1 0 0 0

2 2 1 0 0

3 3 1 0 0

step 3 - now we will traverse each row and check for the max area

#include<bits/stdc++.h>

using namespace std;

Time complexity = O(n^2) if we use count sort for sorting rows otherwise it will be O(n^2*log(n)).

Extra space = O(n^2)

with any other column.

Ex- 0 1 0 1 0

0 1 0 1 1

1 1 0 1 0

the largest rectangle's area is 6 in this case because we can swap column 2 with column 3 so

the matrix after swapping will be

0 0 1 1 0

0 0 1 1 1

1 0 1 1 0

#### Solution -

step 1 - first of all we have to calculate no of consecutive 1's in any particular column so we will take a 2D arrayto store them

so for this the values in array will be

0 1 0 1 0

0 2 0 2 1

1 3 0 3 0

so the mechanism of filling the array will

ar[i][j] = ar[i-1][j]+1 if i>0 && a[i][j]==1

= 1 if i==0 && a[i][j]=1

= 0 else

step 2 - we will sort the rows in decreasing fashion

so after sorting step the matrix will be

1 1 0 0 0

2 2 1 0 0

3 3 1 0 0

step 3 - now we will traverse each row and check for the max area

#include<bits/stdc++.h>

using namespace std;

```
int n;
int rect(int a[][100]){
int i,j;
int ar[n+1][n+1];
//constructing the histogram
for(i=0;i<n;i++){
ar[0][i]=a[0][i]; // if we are in the first row
for(j=1;j<n;j++){
if(a[j][i]==0){
ar[j][i]=0;
}else{
ar[j][i]=ar[j-1][i]+1;
}
}
}
int k;
//sorting rows
//using count sort for better time complexity
for(i=0;i<n;i++){
int br[n+1]={0},x=0;
for(j=0;j<n;j++){
br[ar[i][j]]++; // counting occurrence
}
for(j=n;j>=0;j--){
if(br[j]>0){
for(k=0;k<br[j];k++){
ar[i][x]=j;
x++;
}
}
}
}
//checking for the maximum value
int x;
int max=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
x=(j+1)*ar[i][j];
if(x>max){
max=x;
}
}
}
return max;
}
int main(){
int b,c,d,i,j,a[100][100];
scanf("%d",&n);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
printf("area of the biggest rectangle is = %d\n",rect(a));
return 0;
}
```

` `

Time complexity = O(n^2) if we use count sort for sorting rows otherwise it will be O(n^2*log(n)).

Extra space = O(n^2)

When the sadness is surging in the chest, the warm will come in time, and ease the pain in your heart. This is life.

ReplyDelete_________________________

I find a funny game,let'go!

But I even have this higher, you'll take a look: RS Gold and rsgoldfast.com