Longest increasing subsequence in a 2D matrix.

Question

I am solving a programming challenge to find the length of longest increasing subsequence in a 2D NxN matrix. Both row and columns must increase in each element of a sequence (no need to be consecutive) . I solved it with Dynamic programming approach but it is O(N^4) and inefficient. However, there are many solutions in O(N^3). One such solution is:

   scanf("%d", &N);
    for(i = 1; i <= N; i++) {
        for(j = 1; j <= N; j++) {
            scanf("%d", &L[i][j]);
        }
    }
    Answer = 0; 

    memset(maxLength,0,sizeof(maxLength));
    for (i=1;i<=N;i++) 
    {
        maxLength[1][i] = 1;
        maxLength[i][1] = 1;
    }

    //
    for (i=2;i<=N;i++)
    {

        memset(minValue,0,sizeof(minValue));
        curLen = 1;
        minValue[1] = L[i-1][1]; 

        for (j=2;j<=N;j++)  
        {
            for (p=1;p<i;p++)
            {
                tmpLen = maxLength[p][j-1];
                if (minValue[tmpLen] == 0)
                {
                    minValue[tmpLen] = L[p][j-1]; 
                    curLen = tmpLen;
                }
                else if (minValue[tmpLen]>L[p][j-1])
                {
                    minValue[tmpLen] = L[p][j-1];
                }
            }


            max = 1;
            for (p=curLen;p>0;p--)
            {
                if (L[i][j]>=minValue[p])
                {
                    max = p+1;
                    break;
                }
            }

            maxLength[i][j] = max;
            Answer = Answer>max?Answer:max;
        }
    }

    // Print the answer to standard output(screen).
    printf("%d\n", Answer);

Can someone explain how it works or any other O(N^3) approach ? i can't follow it at all :(.

Ami Tavory Ami Tavory · Accepted Answer · 2016-01-27T10:49:51

It's not that difficult to solve this in O(n³) time. I didn't read the source code, however, so I don't know if the following is what it did, but here is an idea of how it could be done.

The trick is in the update procedure. I guess what you originally did is the following.

Say you are considering an element in the orange rectangle. The previous step has to originate from the blue rectangle (which you already solved). This yields a correct answer, but it's easy to see that it will yield a Θ(n⁴) result, as you can make both the orange and blue rectangles Θ(n²), and you need to consider all pairs between them. (It's easy to formalize this.)

Instead, start by solving only the first row and the first column. In fact, in each iteration, take the next unsolved row and column, and solve them from the previously solved parts.

Here's the trick (which I'll leave to you). If you store enough information in the cells (or in auxiliary data structures, it doesn't matter), then for each element in the orange column you're considering, you only need to look at the column to the left of it (ditto for the orange row - you only need to look at elements in the row above it).

So there are O(n) outer iterations (in each one you consider a row and a column). Each such row/column has O(n) elements, and each left/up row/column has O(n) elements two. The multiplication gives your target complexity.

Longest increasing subsequence in a 2D matrix.

1 Answers