given a matrix of N rows and M columns, each element of matrix is equal to 0 or 1 . we can swap any two rows of matrix any number of times. we are required to find the maximum area of a submatrix consisting of 1's only by swapping rows. constraints (1<=n,m<=5000) problem link: https://www.hackerearth.com/challenge/college/execute-final-round/algorithm/47da7e50ba054fdcb66c292b7f681fb5/ please help and thanks in advance.
For ai, j we calculate pi, j which is position of next 0 element in a row. If ai, j == 0, pi, j == j. If there is no 0 next in a row, pi, j = m.
For example for matrix
0 1 0
1 1 1
0 0 0
We get
0 2 2
3 3 3
0 1 2
Now for each column j sort all pi, j - ai, j and count cntw — number of elements which is greater than w for w in 1..m. Answer is max(w * cntw). It's solution for O(n2 * logn)
thanks a lot got it accepted now
Build a dp array where dp[i][j] denotes maximum no of consecutive ones in row i, starting at column index j.
Now sort the dp values for each column, and rest part is easy. It works in O(n2log(n))