Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [
9
,9,4],
  [
6
,6,8],
  [
2
,
1
,1]
]

Return4
The longest increasing path is[1, 2, 6, 9].

Example 2:

nums = [
  [
3
,
4
,
5
],
  [3,2,
6
],
  [2,2,1]
]

Return4
The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

tag: DFS, memorization

class Solution {
    int ans = Integer.MIN_VALUE;
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int n = matrix.length, m = matrix[0].length;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                dfs(matrix, i, j, new int[n][m]);        
            }
        }


        return ans;
    }

    private int dfs(int[][] matrix, int x, int y, int[][] hash){

        if (hash[x][y] > 0) return hash[x][y];

        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        hash[x][y] = 1;
        int curMax = 0;
        for (int i = 0; i < 4; i++){
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= matrix.length || yy < 0 || yy >= matrix[0].length || matrix[xx][yy] <= matrix[x][y]) continue;

            curMax = Math.max(curMax, dfs(matrix, xx, yy, hash));
        }
        hash[x][y] += curMax;
        //System.out.println("x: " + x + " y: " + y + " val: " + hash[x][y]);
        ans = Math.max(ans, hash[x][y]);

        return hash[x][y];
    }
}