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:
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.

2. Implementation

(1) DFS + memoinzation
class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int m = matrix.length, n = matrix[0].length;
int[][] cache = new int[m][n];
int maxLen = 1;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int len = getLengthOfIncreasingPath(i, j, matrix, cache, directions);
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}
public int getLengthOfIncreasingPath(int row, int col, int[][] matrix, int[][] cache, int[][] directions) {
if (cache[row][col] != 0) {
return cache[row][col];
}
int curMaxLen = 1;
for (int[] direction : directions) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (isValid(row, col, nextRow, nextCol, matrix)) {
int len = 1 + getLengthOfIncreasingPath(nextRow, nextCol, matrix, cache, directions);
curMaxLen = Math.max(curMaxLen, len);
}
}
cache[row][col] = curMaxLen;
return curMaxLen;
}
public boolean isValid(int curRow, int curCol, int nextRow, int nextCol, int[][] matrix) {
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[curRow][curCol] < matrix[nextRow][nextCol];
}
}

3. Time & Space Complexity

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