60ms C++ beat 100%. Elegant and concise code.


  • 5
    F
    class Solution {
        vector<vector<int>> visited;
        int height = 0, width = 0;
        int floodfill(vector<vector<int>>& matrix, int cur, int i, int j)
        {
            if (i < 0 || i >= height || j < 0 || j >= width )
                return 0;
            if (matrix[i][j] <= cur)
                return 0;
            if (visited[i][j] > 0)
                return visited[i][j];
            int r = floodfill(matrix, matrix[i][j], i + 1, j);
            int l = floodfill(matrix, matrix[i][j], i - 1, j);
            int u = floodfill(matrix, matrix[i][j], i, j + 1);
            int d = floodfill(matrix, matrix[i][j], i, j - 1);
            visited[i][j] = max(r, max(l, max(u, d))) + 1;
            return visited[i][j];
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if (matrix.empty())
                return 0;
            height = matrix.size(), width = matrix[0].size();
            visited.resize(height, vector<int>(width));
            int max_len = 0;
            for (int i = 0; i < height; ++i)
                for (int j = 0; j < width; ++j)
                    max_len = max(max_len, floodfill(matrix, INT_MIN, i, j));
            return max_len;
        }
    };

  • 0
    Z

    Your solution looks be a DP one, much cleaner than DFS.


Log in to reply
 

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