329 Longest Increasing Path in a Matrix

1. Question

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:
1
nums = [
2
[9,9,4],
3
[6,6,8],
4
[2,1,1]
5
]
Copied!
Return4 The longest increasing path is[1, 2, 6, 9].
Example 2:
1
nums = [
2
[3,4],5],
3
[3,2,6],
4
[2,2,1]
5
]
Copied!
Return4 The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

2. Implementation

(1) DFS + memoinzation
1
class Solution {
2
public int longestIncreasingPath(int[][] matrix) {
3
if (matrix == null || matrix.length == 0) {
4
return 0;
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
int[][] cache = new int[m][n];
9
int maxLen = 1;
10
11
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
12
13
for (int i = 0; i < m; i++) {
14
for (int j = 0; j < n; j++) {
15
int len = getLengthOfIncreasingPath(i, j, matrix, cache, directions);
16
maxLen = Math.max(maxLen, len);
17
}
18
}
19
return maxLen;
20
}
21
22
public int getLengthOfIncreasingPath(int row, int col, int[][] matrix, int[][] cache, int[][] directions) {
23
if (cache[row][col] != 0) {
24
return cache[row][col];
25
}
26
27
int curMaxLen = 1;
28
29
for (int[] direction : directions) {
30
int nextRow = row + direction[0];
31
int nextCol = col + direction[1];
32
33
if (isValid(row, col, nextRow, nextCol, matrix)) {
34
int len = 1 + getLengthOfIncreasingPath(nextRow, nextCol, matrix, cache, directions);
35
curMaxLen = Math.max(curMaxLen, len);
36
}
37
}
38
39
cache[row][col] = curMaxLen;
40
return curMaxLen;
41
}
42
43
public boolean isValid(int curRow, int curCol, int nextRow, int nextCol, int[][] matrix) {
44
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[curRow][curCol] < matrix[nextRow][nextCol];
45
}
46
}
Copied!

3. Time & Space Complexity

DFS + memoinzation: 时间复杂度O(mn),空间复杂度O(mn)