Untitled

class Solution {
private:
    int m, n;
    bool validPos(int i, int j){
        if(i<0 || j <0 || i>=m || j>=n){
            return false;
        }
        return true;
    }
    int helper(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& mem){
        if(!validPos(i, j)){
            return 0;
        }
        if(mem[i][j]!=0){
            return mem[i][j];
        }
        vector<int> resVec;
        if(validPos(i+1, j) && matrix[i+1][j] > matrix[i][j]){
            resVec.push_back(helper(matrix, i+1, j, mem));
        }
        if(validPos(i, j+1) && matrix[i][j+1] > matrix[i][j]){
            resVec.push_back(helper(matrix, i, j+1, mem));
        }
        if(validPos(i-1, j) && matrix[i-1][j] > matrix[i][j]){
            resVec.push_back(helper(matrix, i-1, j, mem));
        }
        if(validPos(i, j-1) && matrix[i][j-1] > matrix[i][j]){
            resVec.push_back(helper(matrix, i, j-1, mem));
        }
        int temp = 0;
        if(resVec.size()){
            temp = *max_element(resVec.begin(), resVec.end());
        }
        return mem[i][j] = 1 + temp;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        if(!m){
            return 0;
        }
        n = matrix[0].size();
        vector<vector<int>> mem(m,vector<int>(n,0));
        int res = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                helper(matrix, i, j, mem);
                res = max(res, mem[i][j]);
            }
        }
        return res;
    }
};