Largest row-wise and column-wise sorted submatrix — Help Needed

Revision en1, by kstheking, 2020-10-31 09:33:59

This is yet another Interview question of Media.net. Trying to apply dp on this is hard and I can't solve it. I looked up solutions on stackoverflow and GeeksforGeeks but they are all wrong. Can anyone give a correct approach or an idea on how to solve it please?

Problem: Given a matrix N by M, The task is to find the area wise largest rectangular sub-matrix such that each column and each row of the submatrix is strictly increasing

Example:
{{1, 2, 3},
{4, 5, 6},
{1, 2, 3}}

Output: 6

Explanation: The largest sorted submatrix is
{{1, 2, 3},
{4, 5, 6}}

Here are some cases in which the given solutions on the above mentioned sites fail

Case 1

{{1, 4},
{2, 3}}
Correct output: 2

Case 2

{{1, 2, 3},
{0, 5, 6},
{1, 2, 3}}
Correct output: 4

Explanation: The largest sorted submatrix is

{{2, 3},
{5, 6}}

Tags #interview, #dynamic programming, #matrix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English kstheking 2020-10-31 09:33:59 1004 Initial revision (published)