Modular Java Solution


  • 0
    S
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix == null || matrix.length == 0) return 0;
            
            int[][] results = new int[matrix.length][matrix[0].length];
            //for each element get longest streak and capture the max value
            int longestStreak = 0;
            for(int i=0; i<matrix.length; i++){
                for(int j=0; j<matrix[i].length; j++){
                    int curLongestStreak = longestStreak(null, i, j, matrix, results);
                    longestStreak = Math.max(longestStreak, curLongestStreak);
                }
            }
            
            return longestStreak;
        }
        
        public int longestStreak(Integer source, int rowIndex, int columnIndex, int[][] matrix, int[][] results){
            if(!validIndexes(rowIndex, columnIndex, matrix)) return 0;
            
            int newSource = matrix[rowIndex][columnIndex];
            if(source != null && newSource <= source ) return 0; //must be increasing
            
            if(results[rowIndex][columnIndex] != 0) return results[rowIndex][columnIndex];
            
            int leftLongestStreak = longestStreak(newSource, rowIndex, columnIndex-1, matrix, results);
            int rightLongestStreak = longestStreak(newSource, rowIndex, columnIndex+1, matrix, results);
            int topLongestStreak = longestStreak(newSource, rowIndex-1, columnIndex, matrix, results);
            int bottomLongestStreak = longestStreak(newSource, rowIndex+1, columnIndex, matrix, results);
            results[rowIndex][columnIndex] = 1+max(leftLongestStreak, rightLongestStreak, topLongestStreak, bottomLongestStreak);
            return results[rowIndex][columnIndex];
        }
        
        public boolean validIndexes(int rowIndex, int columnIndex, int[][] matrix){
            if(rowIndex < 0 || columnIndex < 0) return false;
            if(rowIndex >= matrix.length) return false;
            if(columnIndex >= matrix[rowIndex].length) return false;
            return true;
        }
        
        public int max(int... args){
            int max = 0;
            for(int arg : args){
                max = Math.max(max, arg);
            }
            return max;
        }
    

Log in to reply
 

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