Longest Increasing Path in a Matrix LeetCode solution in Java

1
class Solution {
2
  public int longestIncreasingPath(int[][] matrix) {
3
    int[][] memo = new int[matrix.length][matrix[0].length];
4
    int longestPath = 0;
5
    for (int i = 0; i < matrix.length; i++) {
6
      for (int j = 0; j < matrix[0].length; j++) {
7
        dfs(matrix, i, j, memo);
8
        longestPath = Math.max(longestPath, memo[i][j]);
9
      }
10
    }
11
    return longestPath;
12
  }
13

14
  private void dfs(int[][] matrix, int i, int j, int[][] memo) {
15
    if (memo[i][j] != 0) return;
16
    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
17
    int max = 0;
18
    for (int k = 0; k < dirs.length; k++) {
19
      int x = dirs[k][0] + i;
20
      int y = dirs[k][1] + j;
21
      if (isValid(matrix, x, y) && matrix[x][y] > matrix[i][j]) {
22
        // Get/compute the largest path for that index
23
        if (memo[x][y] == 0) { // If longest path doesn't exist for that path then compute it
24
          dfs(matrix, x, y, memo);
25
        }
26
        max = Math.max(max, memo[x][y]);
27
      }
28
    }
29
    memo[i][j] = 1 + max;
30
  }
31

32
  private boolean isValid(int[][] matrix, int i, int j) {
33
    if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) return false;
34
    return true;
35
  }
36
}