Simple C++ solution. I wonder, can this be done in-place?


  • 0
    S
    class Solution {
        int path(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& paths){
            if(paths[i][j]!=0) return paths[i][j];
            int cur=matrix[i][j];
            paths[i][j]=1;
            int maxPath=0;
            if(i>0&&matrix[i-1][j]<cur) maxPath=max(maxPath, path(i-1,j,matrix, paths));
            if(j>0&&matrix[i][j-1]<cur) maxPath=max(maxPath, path(i,j-1,matrix, paths));
            if(i<matrix.size()-1&& matrix[i+1][j]<cur) maxPath=max(maxPath, path(i+1,j,matrix, paths));
            if(j<matrix[0].size()-1&& matrix[i][j+1]<cur) maxPath=max(maxPath, path(i,j+1,matrix, paths));
            paths[i][j]+=maxPath;
            return paths[i][j];
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            //mark nodes as visited
            if(matrix.empty()||matrix[0].empty()) return 0;
            int n=matrix.size(),m=matrix[0].size();
            int longest=0;
            vector<vector<int>> paths(n, vector<int>(m, 0));
            for(int i=0;i<n;++i){
                for(int j=0;j<m;++j){
                    if(paths[i][j]==0) longest=max(longest, path(i,j,matrix,paths));
                }
            }
            return longest;
        }
    };

Log in to reply
 

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