Skip to content

329. Longest Increasing Path in a Matrix 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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>> mem(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, mem));

    return ans;
  }

 private:
  // mem[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>>& mem) {
    if (i < 0 || i == matrix.size() || j < 0 || j == matrix[0].size())
      return 0;
    if (matrix[i][j] <= prev)
      return 0;
    int& ans = mem[i][j];
    if (ans > 0)
      return ans;

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int longestIncreasingPath(int[][] matrix) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int ans = 0;
    // mem[i][j] := the LIP starting from matrix[i][j]
    int[][] mem = 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, mem));

    return ans;
  }

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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))