Straightforward Java solution


  • 0
    J
    public class Solution {
        
        int maxLen;
        int[][] memo;
        
        public int longestIncreasingPath(int[][] matrix) {
            
            if(matrix.length<1) return 0;
            memo = new int[matrix.length][matrix[0].length];
            
            for(int i=0;i<matrix.length;i++)
                for(int j=0;j<matrix[0].length;j++)
                 longestHelperFun(matrix,i,j,0,Integer.MIN_VALUE);
            return maxLen;
        }
        
       
        public int longestHelperFun(int [][] matrix,int i,int j,int count,int prev){
            
            if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length) return count;
            
            if(matrix[i][j]<=prev) return count;
            
            if(memo[i][j]!=0) return memo[i][j]+count;
            
            int left =longestHelperFun(matrix,i,j-1,count+1,matrix[i][j]);
            int down =longestHelperFun(matrix,i+1,j,count+1,matrix[i][j]);
            int up= longestHelperFun(matrix,i-1,j,count+1,matrix[i][j]);
            int right=longestHelperFun(matrix,i,j+1,count+1,matrix[i][j]);
            
            int maxChild=Math.max(Math.max(up,down),Math.max(left,right));
            memo[i][j]=maxChild-count;
            
            maxLen= Math.max(maxLen,maxChild);
            return maxChild;
            
        }
    }
    

Log in to reply
 

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