matrix dark arrows = DFS path · yellow = bigger neighbours
dp cached path length from each cell
Call stack bottom → top
private int ROWS, COLS;private int[][] matrix, dp; // dp[r][c]: best path from (r, c), 0 = unknownpublic int longestIncreasingPath(int[][] matrix) { this.matrix = matrix; ROWS = matrix.length; COLS = matrix[0].length; dp = new int[ROWS][COLS]; int longest = 0; for (int r = 0; r < ROWS; r++) { for (int c = 0; c < COLS; c++) { longest = Math.max(longest, dfs(r, c, -1)); } } return longest;}private int dfs(int r, int c, int prevVal) { if (r < 0 || r == ROWS || c < 0 || c == COLS || matrix[r][c] <= prevVal) { return 0; } if (dp[r][c] != 0) { return dp[r][c]; } int res = 1; res = Math.max(res, 1 + dfs(r + 1, c, matrix[r][c])); res = Math.max(res, 1 + dfs(r - 1, c, matrix[r][c])); res = Math.max(res, 1 + dfs(r, c + 1, matrix[r][c])); res = Math.max(res, 1 + dfs(r, c - 1, matrix[r][c])); dp[r][c] = res; return res;}
- r, c
- —
- matrix[r][c]
- —
- res
- —
- memo hits
- 0
Why it works
- Brute force runs a fresh DFS from every cell and explores every increasing path. Paths overlap heavily, so the work can grow exponentially with the matrix size.
- A cell's answer never changes. The longest increasing path starting at
(r, c)only climbs to bigger values, so it cannot loop back through the current path, and it does not depend on how you arrived. Compute it once: 1 + the best answer among bigger neighbours, then cache it. - Complexity: each cell is expanded once and checks 4 neighbours; every later visit is a memo hit. O(m·n) time, and O(m·n) space for the cache and the recursion depth.
- Pitfall: no
visitedset is needed, because strictly increasing paths cannot revisit a cell. But the comparison must be strict: with<instead of<=, equal neighbours would recurse forever. - Alternative: treat cells as a DAG (edges go uphill) and peel it with a topological sort from the local maxima down; the number of BFS layers is the answer.