*Java* DFS + DP with explanations O(mn) 19ms


  • 4
    E

    Key idea: compute the longest length starting from every index (i, j) in the matrix. This can be done by DFS. That is, at location (i, j), we have 4 possible increasing directions, so we check every direction. If one direction satisfies the increasing requirement, increase longest[i][j] by 1. We stop searching when we reach a local maximum. Here, a local maximum refers to the index where none of its four neighbors is less than it. The helper function is to compute the longest length starting from (i, j). We store longest[i][j] once it is computed.

    We don't know where the ultimate longest length starts from, so we need to check every possible index if it is not already computed, and that's what the for loop in the main function is about.

    As of time complexity, we check every index only once, so time complexity is O(mn).

    A final little detail, the original matrix is expanded so that we don't need to consider all kinds of boundary issues. If original matrix is

    *  *  *  *
    *  *  *  *
    *  *  *  *
    

    The extended matrix would be like follows:

    0  ∞  ∞  ∞  ∞  0
    ∞  *  *  *  *  ∞
    ∞  *  *  *  *  ∞
    ∞  *  *  *  *  ∞
    0  ∞  ∞  ∞  ∞  0
    

    Ideally the four corners should be ∞ but since it does not matter (it is not reachable in the code), I will leave it as is. Thanks to @dietpepsi for pointing out the mistake in my previous extended matrix

    public int longestIncreasingPath(int[][] matrix) {
        int rows = matrix.length;
        if(rows<1) return 0;
        int cols = matrix[0].length;
        int[][] matrixExt = new int[rows+2][cols+2], longest = new int[rows+2][cols+2]; // extended matrix and result matrix
        for(int i=1; i<rows+1; i++) {
            matrixExt[i][0] = matrixExt[i][cols+1] = 0x7fffffff;
            for(int j=1; j<cols+1; j++) {
            	matrixExt[0][j] = matrixExt[rows+1][j] = 0x7fffffff;
                matrixExt[i][j] = matrix[i-1][j-1];
            }
        }
    
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 4 different directions
        int max = 1;
        for(int i=1; i<rows+1; i++) {
            for(int j=1; j<cols+1; j++) {
                int temp = helper(matrixExt, longest, dirs, rows, cols, i, j);
                max = temp > max ? temp : max;
            }
        }
        return max;
    }
    
    private int helper(int[][] matrix, int[][] longest, int[][] dirs, int rows, int cols, int i, int j) {
        if(longest[i][j]>0) return longest[i][j]; // reuse
        int max = 1; // result
        for(int[] d : dirs) {
            if(matrix[i][j] > matrix[i+d[0]][j+d[1]]) {
                int temp = helper(matrix, longest, dirs, rows, cols, i+d[0], j+d[1]) + 1; // recursively update longest[i][j]
                max = temp > max ? temp : max;
            }
        }
        longest[i][j] = max; // store for reuse
        return max;
    }

  • 1

    Your matrixExt didn't work as it should. Otherwise, you wouldn't need the boundary check

        if(i==0 || i==rows+1 || j==0 || j==cols+1) return 0; // margins
    

    Because it wouldn't reach the margin.

    I think you should consider rewrite this part

    for(int i=0; i<rows; i++) {
        matrixExt[i][0] = matrixExt[i][cols+1] = 0x7fffffff; // WRONG INDEXES!!!!!!
        for(int j=0; j<cols; j++) {
            matrixExt[0][j] = matrixExt[rows+1][j] = 0x7fffffff; //WRONG INDEXES!!!!!!
            matrixExt[i+1][j+1] = matrix[i][j];
        }
    }
    

    Into

    for(int i=0; i<rows; i++) {
        matrixExt[i+1][0] = matrixExt[i+1][cols+1] = 0x7fffffff; // CORRECT INDEXES!!!!!!
        for(int j=0; j<cols; j++) {
            matrixExt[0][j+1] = matrixExt[rows+1][j+1] = 0x7fffffff; // CORRECT INDEXES!!!!!!
            matrixExt[i+1][j+1] = matrix[i][j];
        }
    }
    

    Or something like this:

    for(int i=0; i<rows+2; ++i)
        matrixExt[i][0] = matrixExt[i][cols+1] = Integer.MAX_VALUE;
    
    for(int j=0; j<cols+2; ++j)
        matrixExt[0][j] = matrixExt[rows+1][j] = Integer.MAX_VALUE;
    
    for(int i=0; i<rows; i++)
        for(int j=0; j<cols; j++)
            matrixExt[i+1][j+1] = matrix[i][j];
    

    Then you may remove that "margins" line.


  • 0
    E

    Thanks for the comment. Actually, that margin line was treated as a base case because we cannot start from the extended boundary. For the boundary condition, I was talking about the for loop in helper. If matrix is not extended, we need to check for the boundary condition in the for loop and it would reduce efficiency.


  • 0

    Yes. I understand what you are trying to do with the matrixExt. But you didn't get what I said.

    In your plan, the matrix, for example:

    1  1
    2  3 
    

    will become

    0    inf   inf    0
    inf  1     1     inf
    inf  2     3     inf
    0    inf   inf    0
    

    If so, it is totally ok.

    However, your code produces this:

    inf  inf   0      inf
    inf   1    1      inf
    0     2    3      0
    inf  inf   0      0
    

    Because your indexes are WRONG when you set those INT_MAXes.
    It should be [i+1] and [j+1] instead of [i] and [j] for the matrixExt!

    You may wonder why you still get AC. That is because your "margins" line saved you.

    if(i==0 || i==rows+1 || j==0 || j==cols+1) return 0; // margins
    

    Even if all boundaries are set to zero as the default. The margins line will still make the code right.

    And if you set the "INF" boundaries correctly, you CAN REMOVE that margins line. Because you will never enter those areas since they are INT_MAX!

    But you have both. Therefore, you can either stop setting the boundary to INT_MAX or stop using "margins".


  • 0
    E

    I see the problem now. I have corrected the mistake in the code now. Thanks for pointing it out!


  • 0

    Hi @dietpepsi, since you authored the problem, I wanted to ask you how we could solve the problem using bottom-up DP instead of top-down DP. Any suggestion? Some guy suggested that you can use topological sort to get the right processing order...


  • 0

    Yes. You can do that. I even have a code running bottom up. It's just not worth it...

    And you are right, you need toposort and then solve. That's why it's not worth it. The top down is more intuitive and less code and faster...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.