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

• ``````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;
}
};``````

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