Quite simple recursive yet accepted as best in cpp


  • 0

    Memorization and DFS combination, hack it and accelerate it meantime!


    class Solution {
    private:
        int rowSize, colSize;
        int traverse(const vector<vector<int>>& matrix, vector<vector<int>>& max_lengths, int r, int c)
        {
            if(max_lengths[r][c]) return max_lengths[r][c];
            int longest = 1;
            if(r-1>-1 && matrix[r][c]>matrix[r-1][c]) longest = max(longest, traverse(matrix, max_lengths, r-1, c)+1);
            if(c-1>-1 && matrix[r][c]>matrix[r][c-1]) longest = max(longest, traverse(matrix, max_lengths, r, c-1)+1);
            if(r+1<rowSize && matrix[r][c]>matrix[r+1][c]) longest = max(longest, traverse(matrix, max_lengths, r+1, c)+1);
            if(c+1<colSize && matrix[r][c]>matrix[r][c+1]) longest = max(longest, traverse(matrix, max_lengths, r, c+1)+1);
            return max_lengths[r][c]=longest;
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            rowSize = matrix.size();
            if(!rowSize) return 0; 
            colSize = matrix[0].size();
            int longest = 0;
            vector<vector<int>> max_lengths(rowSize, vector<int>(colSize, 0));
            for(int r = 0; r < rowSize; r++)
                for(int c = 0; c < colSize; c++)
                    longest = max(longest, traverse(matrix, max_lengths, r, c));
            return longest;
        }
    };

Log in to reply
 

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