Here shows 4 Approaches to slove this problem: BFS, Memorization DFS, DP, Topological Sorting.
BFS
The simplest method that comes to my mind is BFS. We start search from each node, spread out like water, to see how far it can flood, and record the maximum flood path length of all nodes.
if (matrix[nextX][nextY] <= matrix[curPos[0]][curPos[1]]) { continue; }
queue.offer(newint[]{nextX, nextY}); } } }
return ans; } }
Analysis
Time Complexity: O(m2n2).
Space Complexity: O(mn).
Memory + DFS
It’s easy to figure out that there are some repeated enqueuing in BFS method.
Take a example, when searching the longest path of 2, the longest path of 6 will also be searched. However, we will search 6 again as a starting node in BFS.
So how to prune the search?
If we search 6 first and store the result. When search 2, we can know the result is len(2)+len(6).
So we can use a memory to store the result, use DFS to search the longest path of each node.
classSolution{ publicintlongestIncreasingPath(int[][] matrix){ int row = matrix.length; int col = matrix[0].length; if (row == 1 && col == 1) { return1; }
int max = 0; int[][] memo = newint[row][col];
for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (memo[i][j] == 0) { max = Math.max(max, dfs(matrix, memo, i, j)); } } }
return max; }
publicintdfs(int[][] matrix, int[][] memo, int x, int y){ if (memo[x][y] > 0) { return memo[x][y]; }
classSolution{ publicintlongestIncreasingPath(int[][] matrix){ int row = matrix.length; int col = matrix[0].length; if (row == 1 && col == 1) { return1; }
int max = 1;
List<int[]> numList = new ArrayList<>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { numList.add(newint[]{matrix[i][j], i, j}); } }
classSolution{ publicintlongestIncreasingPath(int[][] matrix){ int row = matrix.length; int col = matrix[0].length; if (row == 1 && col == 1) { return1; }
Queue<int[]> queue = new LinkedList<>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (outDegrees[i][j] == 0) { queue.offer(newint[]{i, j}); } } }
int max = 0; while (!queue.isEmpty()) { max++; int size = queue.size(); for (int i = 0; i < size; i++) { int[] curPos = queue.poll(); int x = curPos[0]; int y = curPos[1]; for (int[] dir : dirs) { int prevX = x + dir[0]; int prevY = y + dir[1];