Sharing my 92ms C++ solution


  • 0
    T
    class Solution {
    private:
        int longestIncreasingPathHelper(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& count, int& result)
        {
            int m = matrix.size();
            int n = matrix[0].size();
            
            if(count[i][j]>0)
                return count[i][j];
                
            int nUp=1, nDown=1, nLeft=1, nRight=1;
            
            if(i-1>=0 && matrix[i-1][j]>matrix[i][j])
                nUp = 1 + longestIncreasingPathHelper(matrix, i-1, j, count, result);
                
            if(i+1<m && matrix[i+1][j]>matrix[i][j])
                nDown = 1 + longestIncreasingPathHelper(matrix, i+1, j, count, result);
                
            if(j-1>=0 && matrix[i][j-1]>matrix[i][j])
                nLeft = 1 + longestIncreasingPathHelper(matrix, i, j-1, count, result);
                
            if(j+1<n && matrix[i][j+1]>matrix[i][j])
                nRight = 1 + longestIncreasingPathHelper(matrix, i, j+1, count, result);
                
            count[i][j]=1;
            count[i][j] = max(count[i][j], nUp);
            count[i][j] = max(count[i][j], nDown);
            count[i][j] = max(count[i][j], nLeft);
            count[i][j] = max(count[i][j], nRight);
            result = max(result, count[i][j]);
            
            return count[i][j];
        }
        
    public:
        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;
            
            int result = 0;
            vector<vector<int>> count(m, vector<int>(n,0));
            for(int i=0; i<m; i++)
                for(int j=0; j<n; j++)
                    if(count[i][j]==0)
                        longestIncreasingPathHelper(matrix, i, j, count, result);
                        
            return result;
        }
    };

Log in to reply
 

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