How to find the Largest sorted sub matrix (sorted row-wise as well as column-wise) of a given matrix?

user_8925038 0
Viewed 741

Given a matrix of order n*n. I need to find the length of the largest sorted sub-matrix (sorted both in row-wise and column-wise manner in increasing order). I made the following code which is not giving out the correct output because of some error in my logic.

My pseudo code:

arr=[map(int,raw_input().split()) for j in range(n)] #given list
a=[[0 for j in range(n)]for i in range(n)] #empty list
a[0][0]=1
for i in range(n):
    for j in range(1,n):
        if i==0 and arr[i][j-1]<=arr[i][j]: #compare list element with the 
        right element
            a[i][j-1]=a[i][j-1]+1
        if i>0 and arr[i][j-1]>=arr[i-1][j-1]: #compare list element with the 
        top for i>0
            a[i][j-1]=a[i-1][j-1]+1
        if i>0 and arr[i][j-1]<=arr[i][j]: #compare the same element with the 
        right element for i>0
            a[i][j-1]=a[i][j-1]+1
    print maximum number present in a

Given array:

2 5 3 8 3
1 4 6 8 4
3 6 7 9 5
1 3 6 4 2
2 6 4 3 1

expected output=8 (length of maximum sorted sub-matrix)

1 4 6 8

3 6 7 9

is the sub-matrix which is sorted both row-wise and column-wise

What should be my approach?

dynamic-programming algorithm python c++
2 Answers

This can be done by using three nodes for horizontal,vertical and combined(horizontal and vertical) comparison using DP. First let call these matrices v,h and c then initialize all its elements to 1.

    struct node{
    int h,v,c;
    };
    struct node dp[10009][10009];
//Initialize to 1

    for(i-1->n){
    for(j-1->n){
    dp[i][j].h = 1;
    dp[i][j].v = 1;
    dp[i][j].c = 1;
      }
    }

// Then you can try the following pseudo code:

    for(i:1->n){
    if(arr[i][0]>arr[i-1][0]){
        dp[i][0].v += dp[i-1][0].v ;
    }
    for(j:1->n){
    if(arr[0][j]>arr[0][j-1]){
        dp[0][j].v += dp[0][j-1].v ;
    }
    for(i:1->n){
             for(j-:1->n){
                if(arr[i][j]>arr[i-1][j]){
                    dp[i][j].v = dp[i][j].v + dp[i-1][j].v ;
                }
                if(arr[i][j]>arr[i][j-1]){
                    dp[i][j].h = dp[i][j].h + dp[i][j-1].h ;
                }
    if(arr[i][j]>arr[i-1][j] && arr[i][j]>arr[i][j-1] && arr[i-1][j]>arr[i-
     1][j-1] && arr[i][j-1]>arr[i-1][j-1]){
                   dp[i][j].c = solver(i,j);
                }
             }
         }

Edit: Updated the answer by including working script for the problem 

#include<bits/stdc++.h>
using namespace std;
int arr[1050][1050];
int n;
struct node{
int horizontal,vertical,combined;
};
struct node dp[1050][1050];
int solver(int i,int j){
int x = i;
int y = j;
int left = dp[i][j].horizontal - 1;
int up = dp[i][j].vertical - 1;
int range = min(left,up);
int count = 0;
while(count <= range){
 count++;
 x--;
 y--;
 if(dp[x][y].combined ==1)
    break;
}
int tempx = INT_MAX;
int tempy = INT_MAX;
for(int k=x;k<=i;k++){
    tempx=min(tempx,dp[k][y].horizontal-1);
}
for(int z=y;z<=j;z++){
    tempy=min(tempy,dp[x][z].vertical-1);
}
return ((count*count)+count+count+1)+max((i-x+1)*tempx,(j-y+1)*tempy);
}
int solverr(){
   for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
      dp[i][j].horizontal = 1;
      dp[i][j].vertical = 1;
      dp[i][j].combined = 1;

     }
   }
   for(int i=1;i<n;i++){
     if(arr[i][0]>arr[i-1][0]){
        dp[i][0].vertical += dp[i-1][0].vertical ;
     }
   }
   for(int j=1;j<n;j++){
    if(arr[0][j] > arr[0][j-1]){
        dp[0][j].horizontal += dp[0][j-1].horizontal ;
    }
   }
         for(int i=1;i<n;i++){
             for(int j=1;j<n;j++){
                if(arr[i][j]>arr[i-1][j]){
                    dp[i][j].vertical = dp[i][j].vertical + dp[i-1][j].vertical ;
                }
                if(arr[i][j]>arr[i][j-1]){
                    dp[i][j].horizontal = dp[i][j].horizontal + dp[i][j-1].horizontal ;
                }
                if(arr[i][j]>arr[i-1][j] && arr[i][j]>arr[i][j-1] && arr[i-1][j]>arr[i-1][j-1] && arr[i][j-1]>arr[i-1][j-1]){
                    dp[i][j].combined = solver(i,j);
                }
             }
         }

  int res = -1;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        if(res<dp[i][j].horizontal)
            res = dp[i][j].horizontal ;

        if(res<dp[i][j].vertical)
            res = dp[i][j].vertical ;

        if(res<dp[i][j].combined)
            res = dp[i][j].combined ;

    }
  }


  return res;
}
int main(){
int t,ans;
scanf("%d",&t);
while(t--){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
         scanf("%d",&arr[i][j]);
    ans=solverr();
    printf("%d\n",ans);
}
return 0;
}

3

3

3 0 4

1 2 5

4 6 7

3

1 2 5

4 6 7

10 8 3

5

2 5 3 8 3

1 4 6 8 4

3 6 7 9 5

1 3 6 4 2

2 6 4 3 1

output: 6 6 8

user_88013080

correct working solution for the problem!

I have used the concept of max area in the histogram and prefix sum to find the solution.

Above solution if failing for this test c

1 2 5 6
2 3 4 7
3 4 5 8
8 9 10 100
user_90730300
Related