java dfs + memo, 13 ms beats 97%


  • 1
    R

    Basically 2 steps to solve this problem:
    1.start from path[i][j] == 0, which means we haven't visited this point before.
    2.The reason I designed this being DFS is that we need to get the total length starting from where we begin. Here we can use a memo.

    public class Solution {
        public static final int[] delta = new int[]{0,1,0,-1,0};
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) return 0;
            int m = matrix.length, n = matrix[0].length;
            Queue<int[]> q = new LinkedList<>();
            int max = 0;
            int[][] path = new int[m][n];
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(path[i][j] == 0) {
                        max = Math.max(max, walk(path, i, j, matrix));
                    }
                }
            }
            return max;
        }
        
        private int walk(int[][] path, int i, int j, int[][] matrix) {
            if(path[i][j] != 0) return path[i][j];
            int value = 1;
            for(int d = 1; d < delta.length; d++) {
                int newI = i + delta[d];
                int newJ = j + delta[d-1];
                if(newI >= 0 && newI < path.length && newJ >= 0 && newJ < path[0].length
                    && matrix[newI][newJ] > matrix[i][j]) {
                    value = Math.max(value, walk(path, newI, newJ, matrix) + 1);
                }
            }
            path[i][j] = value;
            return value;
        }
    }

Log in to reply
 

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