Help! TLE problem, Could someone give me any tips about questions like this? Thanks


  • 0
    A

    I have read the answers posted here, but could some optimize the code below? and could you tell me the flaws of the idea, and is there any tips to solve questions like this?
    Thanks

     public class Solution {
            public int longestIncreasingPath(int[][] matrix) {
                if(matrix.length == 0){
                    return 0;
                }
                int[] result = new int[1];
                boolean[][] checkBox= new boolean[matrix.length][matrix[0].length];
                result[0] = 1;
                
                for(int row = 0; row < matrix.length; row++){
                    for(int col = 0; col < matrix[0].length; col++){
                        getLongestIncreasingPath(matrix, result, row, col, 1, checkBox);
                    }
                }
                return result[0];
            }
            
            public static void getLongestIncreasingPath(int[][] matrix, int[] result, int row, int col, int tmpLength, 
                                                        boolean[][] checkBox){
                         
                                              
                if(row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length){
                    if(tmpLength > result[0]){
                        result[0] = tmpLength;
                    }
                    return;
                }
                
                int tmp = matrix[row][col];
                checkBox[row][col] = true;
                if(row + 1 < matrix.length && checkBox[row + 1][col] == false && matrix[row + 1][col] > tmp){
                    getLongestIncreasingPath(matrix, result, row + 1, col, tmpLength + 1, checkBox);
                    checkBox[row + 1][col] = false;
                }
                if(row - 1 >= 0 && checkBox[row - 1][col] == false && matrix[row - 1][col] > tmp){
                    getLongestIncreasingPath(matrix, result, row - 1, col, tmpLength + 1, checkBox);
                    checkBox[row - 1][col] = false;
                }
                if(col - 1 >= 0 && checkBox[row][col - 1] == false && matrix[row][col - 1] > tmp){
                    getLongestIncreasingPath(matrix, result, row, col - 1, tmpLength + 1, checkBox);
                    checkBox[row][col - 1] = false;
                }
                if(col + 1 < matrix[0].length && checkBox[row][col + 1] == false && matrix[row][col + 1] > tmp){
                    getLongestIncreasingPath(matrix, result, row, col + 1, tmpLength + 1, checkBox);
                    checkBox[row][col + 1] = false;
                }
            
                
                if(tmpLength > result[0]){
                    result[0] = tmpLength;
                }
                checkBox[row][col] = false;
                return;
            }
            
            
        }

  • 0

    Plain DFS is not enough. You need memoization. If you don't know what that is. Search it on google first.


Log in to reply
 

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