# 60ms C++ solution beats 100%, easy to understand

• ``````class Solution {
public:

int find(vector<vector<int>> &matrix, int i , int j,vector<vector<int>> &start)
{
if(start[i][j] != -1)
return start[i][j];
int a = 0, b = 0, c = 0, d = 0;
if(i > 0 && matrix[i - 1][j] > matrix[i][j])  // up
a = find(matrix, i - 1, j, start);
if(j > 0 && matrix[i][j - 1] > matrix[i][j])  // left
b = find(matrix, i, j - 1, start);
if(i < matrix.size() - 1 && matrix[i + 1][j] > matrix[i][j])  // down
c = find(matrix, i + 1, j, start);
if(j < matrix[0].size() - 1 && matrix[i][j + 1] > matrix[i][j])  // right
d = find(matrix, i, j + 1, start);
start[i][j] = max(max(a, b), max(c, d)) + 1;
return start[i][j];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if(m == 0)
return 0;
int n = matrix[0].size();
if(n == 0)
return 0;
vector<vector<int>> start(m, vector<int>(n, -1));
int maxi;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
maxi = max(maxi, find(matrix, i, j, start));
}
return maxi;
}
};``````

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