60ms C++


  • 0
    S
    int longestIncreasingPath(vector<vector<int>>& matrix) {
            int result = 0;
            int n = matrix.size();
            if(!n)
                return 0;
            int m = matrix[0].size();
            vector<vector<int>> cache(n,vector<int>(m,0));  //stores longest starting at each index
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(!cache[i][j])
                        dfs(matrix,i,j,cache);
                    result = max(result,cache[i][j]);
                }
            }
            return result;
        }
        int dfs(vector<vector<int>>& matrix, int i, int j, vector<vector<int>> &cache){
            if(cache[i][j])
                return cache[i][j];
            int maxlen = 0;
            if(i>0 && (matrix[i-1][j]>matrix[i][j]))
                maxlen = max(maxlen,dfs(matrix,i-1,j,cache));
            if(i<matrix.size()-1 && (matrix[i+1][j]>matrix[i][j]))
                maxlen = max(maxlen,dfs(matrix,i+1,j,cache));
            if(j>0 && (matrix[i][j-1]>matrix[i][j]))
                maxlen = max(maxlen,dfs(matrix,i,j-1,cache));
            if(j<matrix[0].size()-1 && (matrix[i][j+1]>matrix[i][j]))
                maxlen = max(maxlen,dfs(matrix,i,j+1,cache));
            cache[i][j] = 1 + maxlen;
            return 1 + maxlen;
        }
    

Log in to reply
 

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