Java Solution Using HashMap to improve


  • 0
    S
    public class Solution {
        int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        Map<Integer, Integer> map = new HashMap<>();
        int[][] matrix;
        int maxLen = 0;
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
            this.matrix = matrix;
            int row = matrix.length;
            int col = matrix[0].length;
            for(int i=0; i<matrix.length; i++){
                for(int j=0; j<matrix[0].length; j++){
                    maxLen = Math.max(maxLen, dfs(i, j));
                }
            }
            return maxLen;
        }
        
        private int dfs(int i, int j){
            int pos = i*matrix[0].length+j;
            int curMax = 1;
            if(map.containsKey(pos)){
                return map.get(pos);
            }
            for(int[] d:dir){
                if(i+d[0]>=0 && i+d[0]<matrix.length && j+d[1]>=0 && j+d[1]<matrix[0].length){
                    if(matrix[i+d[0]][j+d[1]]<matrix[i][j]){
                        curMax = Math.max(curMax, 1+dfs(i+d[0], j+d[1]));
                    }
                }
            }
            map.put(pos, curMax);
            return curMax;
        }
    }

Log in to reply
 

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