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


  • 0
    W
    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;
        }
    };

Log in to reply
 

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