#329 Longest Increasing Path in a Matrix
frequently reported atByteDance / TikTokMetaGoogleMicrosoftAmazonBloomberg
the problem
In plain words
Given an m × n integer matrix, return the length of the longest strictly increasing path. You may move up, down, left or right (no diagonals, no wrap-around).
in matrix = [[9,9,4],[6,6,8],[2,1,1]]
out 4
1 → 2 → 6 → 9.
in matrix = [[3,4,5],[3,2,6],[2,2,1]]
out 4
3 → 4 → 5 → 6.
- 1 ≤ m, n ≤ 200
- 0 ≤ matrix[i][j] ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternDP on a DAGTopological sort & cycle detection
Draw an edge from each cell to every strictly larger neighbour. Strictly increasing edges can never loop back, so the grid is a DAG — longest path in a DAG is easy.
solutions
From brute force to optimal
Try every increasing walk from every starting cell.
- For each cell, DFS into larger neighbours.
- Return 1 + best child path.
Cells are re-explored once per path that reaches them, and the number of increasing paths can grow exponentially.
Recursion depth up to the path length.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int longestIncreasingPath(int[][] matrix) { int best = 0; for (int r = 0; r < matrix.length; r++) for (int c = 0; c < matrix[0].length; c++) best = Math.max(best, walk(matrix, r, c)); return best; } /** No memo: the same cell is re-explored from every path that reaches it. */ private int walk(int[][] m, int r, int c) { int best = 1; for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < m.length && nc >= 0 && nc < m[0].length && m[nr][nc] > m[r][c]) best = Math.max(best, 1 + walk(m, nr, nc)); } return best; }}The best path starting at a cell never changes — cache it. No visited[] needed because the graph is acyclic.
- memo[r][c] = 0 means unknown.
- dfs = 1 + max dfs over larger neighbours.
- Answer = max over all cells.
Each cell is solved once, with 4 neighbour checks.
Memo table plus recursion depth up to m·n (40 000 frames — fine with LeetCode's stack, risky elsewhere).
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int longestIncreasingPath(int[][] matrix) { int rows = matrix.length, cols = matrix[0].length; int[][] memo = new int[rows][cols]; // 0 = unknown; every real answer is ≥ 1 int best = 0; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) best = Math.max(best, dfs(matrix, r, c, memo)); return best; } private int dfs(int[][] m, int r, int c, int[][] memo) { if (memo[r][c] != 0) return memo[r][c]; int best = 1; for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < m.length && nc >= 0 && nc < m[0].length && m[nr][nc] > m[r][c]) best = Math.max(best, 1 + dfs(m, nr, nc, memo)); } return memo[r][c] = best; // no "visited" needed: strictly increasing edges can't cycle }}Dry run: solve each cell once
In-degree = number of smaller neighbours. Start from local minima; the number of BFS layers equals the longest path.
- Count smaller neighbours for every cell.
- Queue all cells with count 0.
- Process layer by layer, decrementing larger neighbours; count layers.
Every cell enters the queue once; 4 neighbour checks each.
In-degree grid plus queue — and no recursion at all.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int longestIncreasingPath(int[][] matrix) { int rows = matrix.length, cols = matrix[0].length; int[][] indegree = new int[rows][cols]; // number of SMALLER neighbours pointing at me for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] < matrix[r][c]) indegree[r][c]++; } Deque<int[]> queue = new ArrayDeque<>(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (indegree[r][c] == 0) queue.offer(new int[] {r, c}); // local minima int layers = 0; while (!queue.isEmpty()) { layers++; // every BFS layer = one more step on the longest path for (int size = queue.size(); size > 0; size--) { int[] cell = queue.poll(); for (int[] d : DIRS) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[cell[0]][cell[1]] && --indegree[nr][nc] == 0) queue.offer(new int[] {nr, nc}); } } } return layers; }}in the room
How to say it in the interview
talk track
- Say the key sentence: "Strictly increasing means no cycles, so it's longest path in a DAG — memoised DFS works."
- Point out that you don't need a visited set, and why.
- Offer the iterative Kahn-layers version if the interviewer worries about recursion depth.
traps
- Using
>=instead of>— equal neighbours create cycles and infinite recursion. - Adding a visited[] that blocks legitimate re-use of memoised cells.
what they ask next
Follow-ups
Return the path itself, not just its length?
After filling memo, start at a cell with the largest memo. Then keep stepping to a bigger neighbour whose memo is exactly one less. O(m·n) extra work at most.
Diagonal moves are allowed too?
Check 8 neighbours instead of 4. It's still a DAG (values still strictly increase), so the same memo works in O(m·n).
before you submit
Edge cases to test
- All values equal → 1.
- 1 × 1 matrix → 1.
- Values up to 2³¹ − 1: compare with
>, never subtract. - A snake-shaped increasing path can use every cell, so the recursion can be m·n deep.
practise next
Similar problems
- #300Longest Increasing SubsequenceMediumin Dynamic Programming
- #2050Parallel Courses IIIHardin Topo Sort
- #417Pacific Atlantic Water FlowMediumin Graphs