Problem Statement

Given a matrix with 0 and 1’s, find the largest rectangle of all 1’s in the matrix. The rectangle can be formed by swapping any pair of columns of given matrix.

Example:

Input: bool mat[][] = { {0, 1, 0, 1, 0},
                        {0, 1, 0, 1, 1},
                        {1, 1, 0, 1, 0}
                      };
Output: 6
The largest rectangle's area is 6. The rectangle
can be formed by swapping column 2 with 3
The matrix after swapping will be
     0 0 1 1 0
     0 0 1 1 1
     1 0 1 1 0

Input: bool mat[R][C] = { {0, 1, 0, 1, 0},
                         {0, 1, 1, 1, 1},
                         {1, 1, 1, 0, 1},
                         {1, 1, 1, 1, 1}
                      };
Output: 9

Problem Link

Largest area of rectangle with permutations - InterviewBit

Reference Link

Find the largest rectangle of 1's with swapping of columns allowed - GeeksforGeeks

Code

int Solution::solve(vector<vector<int> > &A) {
    
    int m = A.size();
    
    if(m==0)
    return 0;
    
    int n = A[0].size();
    
 
    
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==0)
            continue;
            
            else
            {
                if(A[i][j]!=0)//pillars should have continuous 1's
                A[i][j] += A[i-1][j]; 
            }
        }
    }
    
    for(int i=0;i<m;i++)
    {
        sort(A[i].begin(),A[i].end(),greater<int>());
    }
    
    int maxarea = 0;
    
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            int area = (j+1)*A[i][j];
            maxarea = max(maxarea,area);
        }
    }
    
    return maxarea;
}