LeetCode Solutions

			

class Solution {
 public:
  int longestIncreasingPath(vector<vector<int>>& matrix) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    int ans = 0;
    vector<vector<int>> memo(m, vector<int>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        ans = max(ans, dfs(matrix, i, j, INT_MIN, memo));

    return ans;
  }

 private:
  // memo[i][j] := the LIP starting from matrix[i][j]
  int dfs(const vector<vector<int>>& matrix, int i, int j, int prev,
          vector<vector<int>>& memo) {
    if (i < 0 || i == matrix.size() || j < 0 || j == matrix[0].size())
      return 0;
    if (matrix[i][j] <= prev)
      return 0;
    int& ans = memo[i][j];
    if (ans > 0)
      return ans;

    const int curr = matrix[i][j];
    return ans = 1 + max({dfs(matrix, i + 1, j, curr, memo),
                          dfs(matrix, i - 1, j, curr, memo),
                          dfs(matrix, i, j + 1, curr, memo),
                          dfs(matrix, i, j - 1, curr, memo)});
  }
};

			

class Solution {
  public int longestIncreasingPath(int[][] matrix) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int ans = 0;
    // memo[i][j] := the LIP starting from matrix[i][j]
    int[][] memo = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        ans = Math.max(ans, dfs(matrix, i, j, Integer.MIN_VALUE, memo));

    return ans;
  }

  private int dfs(int[][] matrix, int i, int j, int prev, int[][] memo) {
    if (i < 0 || i == matrix.length || j < 0 || j == matrix[0].length)
      return 0;
    if (matrix[i][j] <= prev)
      return 0;
    if (memo[i][j] > 0)
      return memo[i][j];

    final int curr = matrix[i][j];
    final int a = dfs(matrix, i + 1, j, curr, memo);
    final int b = dfs(matrix, i - 1, j, curr, memo);
    final int c = dfs(matrix, i, j + 1, curr, memo);
    final int d = dfs(matrix, i, j - 1, curr, memo);
    return memo[i][j] = 1 + Math.max(Math.max(a, b), Math.max(c, d));
  }
}

			

class Solution:
  def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
    m = len(matrix)
    n = len(matrix[0])

    @functools.lru_cache(None)
    def dfs(i: int, j: int, prev: int) -> int:
      if i < 0 or i == m or j < 0 or j == n:
        return 0
      if matrix[i][j] <= prev:
        return 0

      curr = matrix[i][j]
      return 1 + max(dfs(i + 1, j, curr),
                     dfs(i - 1, j, curr),
                     dfs(i, j + 1, curr),
                     dfs(i, j - 1, curr))

    return max(dfs(i, j, -math.inf) for i in range(m) for j in range(n))