Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- the DFS here is basically like DP with memorization. Every cell that has been computed will not be computed again,
- only a value look-up is performed. So this is O(mn), m and n being the width and height of the matrix.
- To be exact, each cell can be accessed 5 times at most: 4 times from the top, bottom, left and right and one time
- from the outermost double for loop. 4 of these 5 visits will be look-ups except for the first one.
- So the running time should be lowercase o(5mn), which is of course O(mn).
- To get max length of increasing sequences:
- 1. Do DFS from every cell
- 2. Compare every 4 direction and skip cells that are out of boundary or smaller
- 3. Get matrix max from every cell's max (because each cell will have lengths from four directions)
- 4. Use matrix[x][y] <= matrix[i][j] so we don't need a visited[m][n] array
- 5. The key is to cache the distance because it's highly possible to revisit a cell
- */
- public class Solution {
- public int longestIncreasingPath(int[][] matrix) {
- if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
- int m = matrix.length, n = matrix[0].length;
- int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
- int[][] cache = new int[m][n];
- int max = 0;
- for(int i=0; i<m; i++) {
- for(int j=0; j<n; j++) {
- int len = dfs(matrix, i, j, cache, dirs);
- max = Math.max(max, len);
- }
- }
- return max;
- }
- public int dfs(int[][] matrix, int i, int j, int[][] cache, int[][] dirs) {
- if(cache[i][j] != 0) return cache[i][j];
- int max = 1;
- for(int[] dir : dirs) {
- int x = i + dir[0], y = j + dir[1];
- if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[i][j]) continue;
- int len = 1 + dfs(matrix, x, y, cache, dirs);
- max = Math.max(max, len);
- }
- cache[i][j] = max;
- return max;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement