329. Longest Increasing Path in a Matrix

O(v)???? DFS

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = m ? matrix[0].size() : 0;
        vector<vector<int>> memo(m, vector<int>(n, 0));
        int res = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                res = max(res, helper(matrix, memo, i, j));
        return res;
    }
private:
    vector<int> dir = {0, 1, 0, -1, 0};
    int m, n;
    int helper(vector<vector<int>>& matrix, vector<vector<int>>& memo, int x, int y) {
        if (memo[x][y]) return memo[x][y];

        for (int i = 0; i < 4; i++) {
            int xx = x + dir[i], yy = y + dir[i + 1];
            if (xx < 0 || yy < 0 || xx >= m || yy >= n) continue;
            if (matrix[xx][yy] > matrix[x][y]) 
                memo[x][y] = max(memo[x][y], helper(matrix, memo, xx, yy));
        }

        return ++memo[x][y];
    }
};

BFS

public static class Point{
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public static int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
        return 0;
    int n = matrix.length, m = matrix[0].length, count = m * n, ans = 0;
    while (count > 0) {
        HashSet<Point> remove = new HashSet<Point>();
        // each round, remove the peak number.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == Integer.MIN_VALUE)
                    continue;
                boolean up = (i == 0 || matrix[i][j] >= matrix[i - 1][j]);
                boolean bottom = (i == n - 1 || matrix[i][j] >= matrix[i + 1][j]);
                boolean left = (j == 0 || matrix[i][j] >= matrix[i][j - 1]);
                boolean right = (j == m - 1 || matrix[i][j] >= matrix[i][j + 1]);
                if (up && bottom && left && right)
                    remove.add(new Point(i, j));
            }
        }
        for (Point point : remove) {
            matrix[point.x][point.y] = Integer.MIN_VALUE;
            count--;
        }
        ans++;
    }
    return ans;
}