Longest Increasing Path in a Matrix


class Solution {
public int longestIncreasingPath(int[][] matrix) {if(matrix.length == 0  matrix[0].length==0){ return 0; } int [][] maxpath = new int [matrix.length][matrix[0].length]; for(int i = 0; i < matrix.length; i++){ for(int j = 0; j< matrix[0].length; j++) maxpath[i][j] = 1; } for(int i = 0; i < matrix.length; i++){ for(int j = 0; j< matrix[0].length; j++) findMax(matrix, maxpath, i, j); } int max = 1; for(int i = 0; i < matrix.length; i++){ for(int j = 0; j< matrix[0].length; j++) if(maxpath[i][j]> max){ max = maxpath[i][j]; } } return max; } public void findMax(int[][] matrix, int[][] maxpath, int i, int j){ if(maxpath[i][j] != 1){ return; } int[][] adj = {{0, 1}, {1, 0}, {0, 1}, {1,0}}; int result = 1; for(int k = 0; k < 4; k++){ int newx = i+adj[k][0]; int newy = j+adj[k][1]; if(newx >= 0 && newx < matrix.length && newy >= 0 && newy< matrix[0].length){ if(matrix[newx][newy]> matrix[i][j]){ findMax(matrix, maxpath, newx, newy); if( maxpath[newx][newy] + 1 > result) result = maxpath[newx][newy] + 1; } } } if(result == 1){ maxpath[i][j] = 1; }else{ maxpath[i][j] = result; } }
}

"Usually, in DFS or BFS, we can employ a set visited to prevent the cells from duplicate visits. We will introduce a better algorithm based on this in the next section." but I did not find which part in the article explains why we don't have to maintain such a visited set. My guess is because the path is increasing, we will never visit a node with smaller value.