deepak1527's blog

Help in finding the maximum area of a submatrix
By deepak1527, history, 7 years ago, In English

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.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply