here is only basic implementation of problems for beginners. If you have any problem with any solution or any basic concept of programming or you want more efficient solution you can mail me.
my suggestion is not to copy and paste codes from here try to understand the logic and think why you were not able to solve it.

Saturday 22 August 2015

Finding largest rectangle in a given matrix when swapping of columns is possible

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

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 array
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;
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)





No comments:

Post a Comment