C++ DFS solution with early stopping, 53ms, beats 95%


  • 0
    S
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int rows = matrix.size();
            if(rows == 0){
                return 0;
            }
            int cols = matrix[0].size(), result = 0;
            vector<vector<int>> maxlength(rows, vector<int>(cols, -1));
            
            for(int row = 0; row < rows; row++){
                for(int col = 0; col < cols; col++){
                    if(maxlength[row][col] == -1){
                        maxlength[row][col] = DFS(matrix, maxlength, row, col, 0);
                    }
                    result = max(result, maxlength[row][col]);
                }
            }
            return result;
        }
        
        int DFS(vector<vector<int>> &matrix, vector<vector<int>> &maxlength, int row, int col, int curlen){
            int mlength = 1;
            if(row > 0 && matrix[row][col] < matrix[row-1][col]){
                if(maxlength[row-1][col] != -1){
                    mlength = max(mlength, 1 + maxlength[row-1][col]);
                }
                else{
                    mlength = max(mlength, 1 + DFS(matrix, maxlength, row-1, col, 0));
                }
            }
            if(row < matrix.size() - 1 && matrix[row][col] < matrix[row+1][col]){
                if(maxlength[row+1][col] != -1){
                    mlength = max(mlength, 1 + maxlength[row+1][col]);
                }
                else{
                    mlength = max(mlength, 1 + DFS(matrix, maxlength, row+1, col, 0));
                }
            }
            if(col > 0 && matrix[row][col] < matrix[row][col-1]){
                if(maxlength[row][col-1] != -1){
                    mlength = max(mlength, 1 + maxlength[row][col-1]);
                }
                else{
                    mlength = max(mlength, 1 + DFS(matrix, maxlength, row, col-1, 0));
                }
            }
            if(col < matrix[0].size() - 1 && matrix[row][col] < matrix[row][col+1]){
                if(maxlength[row][col+1] != -1){
                    mlength = max(mlength, 1 + maxlength[row][col+1]);
                }
                else{
                    mlength = max(mlength, 1 + DFS(matrix, maxlength, row, col+1, 0));
                }
            }
            maxlength[row][col] = mlength;
            return mlength;
        }
    };

Log in to reply
 

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