PROBLEM LINK:
Binary Matrix
Induction Code Battle
Author: Akshit Monga
Tester: Akshit Monga
Editorialist: Arjun Kathail
DIFFICULTY:
MEDIUM
PREREQUISITES:
Sorting, Dynamic Programming
PROBLEM:
Chef gives you a matrix A of size N⋅M containing only zeros and ones. In one operation, you can swap any 2 columns. You can apply this operation any number of times.
What is the area (total number of cells) of the largest submatrix of the given matrix containing all ones you can achieve if you apply the operations optimally?
QUICK EXPLANATION:
Create an auxilary matrix and store the count of 1’s in every column (this gives the height of 1s in every column). Sort all the rows in increasing order and then traverse the rows to get the maximum possible area.
Time Complexity: O(n*m*log(m)) or O(n*(n+m)) using counting sort.
EXPLANATION:
Step 1: Start by storing the count of all 1’s in every column in an auxilary matrix.
Example: Given Marix \quad Auxilary Matrix (dp)
\quad\quad\quad\quad\quad 1 0 0 \quad\quad\quad 1 0 0
\quad\quad\quad\quad\quad 1 1 1 \quad\quad\quad 2 1 1
\quad\quad\quad\quad\quad 1 0 1 \quad\quad\quad 3 1 2
Step 2: Sort all the rows in the Auxilary Matrix in increasing order.
\quad Eg: Auxilary Matrix (dp)
\quad\quad\quad 0 0 1
\quad\quad\quad 1 1 2
\quad\quad\quad 1 2 3
Step 3: Traverse all the rows and find the maximum area by simply calculating and storing the maximum of all dp[i][j]*(m-j).
Time Complexity: O(n*m*log(m)) or O(n*(n+m)) using counting sort.
SOLUTIONS:
Setter's Solution
// Author- Akshit Monga
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
int mat[n][m],dp[n][m];
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mat[i][j];
if(mat[i][j]){
dp[i][j]=1;
if(i)dp[i][j]+=dp[i-1][j];
}
else dp[i][j]=0;
}
}
for(int i=0;i<n;i++){
sort(dp[i],dp[i]+m);
for(int j=0;j<m;j++)ans=max(ans,dp[i][j]*(m-j));
}
cout<<ans<<'\n';
}
return 0;
}
Tester's Solution
'''Author- Akshit Monga'''
def largestSubmatrix(matrix):
n = len(matrix)
m = len(matrix[0])
dp = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
for j in range(m):
if matrix[i][j] == 0:
dp[i][j] = 0
else:
assert matrix[i][j]==1
dp[i][j] = 1
if i > 0:
dp[i][j] += dp[i - 1][j]
ans = 0
for i in range(n):
val = sorted(dp[i])
for j in range(m):
ans = max(val[j] * (m - j), ans)
return ans
t = int(input())
assert t<=10
tot=0
for _ in range(t):
n,m=map(int,input().split())
assert n*m<=10**6
mat=[-1 for j in range(n)]
for i in range(n):
mat[i]=[int(x) for x in input().split()]
print(largestSubmatrix(mat))
tot+=n*m
assert tot<=10**6
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FLASH ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main(){
FLASH
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
int mat[n][m], dp[n][m];
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mat[i][j];
if(mat[i][j]){
dp[i][j]=1;
if(i)dp[i][j]+=dp[i-1][j];
}
else dp[i][j]=0;
}
}
for(int i=0;i<n;i++){
sort(dp[i],dp[i]+m);
for(int j=0;j<m;j++)
ans=max(ans, dp[i][j]*(m-j));
}
cout<<ans<<endl;
}
return 0;
}