Longest Increasing Path in Matrix LeetCode 329

LeetCode 329 Longest Increasing Path in a Matrix presents you with an m x n integer matrix. Your task is to find the length of the longest strictly increasing path. From each cell you may move in 4 directions — up, down, left, right — but you may not move diagonally and you may not move outside the matrix boundaries. Each step along the path must visit a cell with a strictly greater integer value than the previous cell.

The brute-force approach — trying DFS from every cell without caching — would recompute the longest path from the same cell repeatedly, leading to O((m*n)^2) or worse time complexity. The key insight is that the strictly increasing constraint guarantees the graph is acyclic: if you start from cell A and reach cell B by a strictly increasing path, you can never return to A. This absence of cycles makes memoization safe and results in each cell being computed exactly once.

The expected output is a single integer — the length of the longest strictly increasing path in the matrix. Note that a path of length 1 (a single cell) is always valid, so the answer is at least 1 for any non-empty matrix.

Many grid DP problems — such as Minimum Path Sum or Unique Paths — work by processing cells in a fixed order (typically top-to-bottom, left-to-right) and building dp[i][j] from dp[i-1][j] and dp[i][j-1]. This works because the recurrence only looks at cells that have already been processed. In LeetCode 329, however, the path can go in any of the 4 directions: a valid increasing path might go right, then down, then left, then up. There is no fixed topological order on the grid coordinates that respects all possible path directions simultaneously.

The root problem is that the dependency graph for this problem is not the grid coordinates themselves but rather the value ordering. A cell at position (2, 0) might depend on a cell at (3, 0) if matrix[3][0] > matrix[2][0]. Processing left-to-right row by row would try to compute dp[2][0] before dp[3][0], which is backwards for this dependency. You need an ordering based on cell values, not positions — which is exactly what DFS memoization or topological sort provides.

Understanding this failure mode helps you recognize a broader class of problems where standard DP ordering breaks down: whenever the dependency direction is determined by values rather than positions, you need either DFS with memoization or an explicit topological sort. Other examples include the Alien Dictionary problem and Parallel Courses from LeetCode.

The DFS memoization solution maintains a memo table memo[i][j] that stores the length of the longest increasing path starting from cell (i, j). Initially all entries are 0 (uncomputed). For each cell, we call dfs(i, j): explore all 4 neighbors (r, c) where matrix[r][c] > matrix[i][j], recursively compute dfs(r, c) for each valid neighbor, and return 1 + max(dfs(r, c)) over all valid neighbors. If no neighbor is strictly greater, the cell has no outgoing edges and returns 1 (path of just itself).

The memoization ensures each cell is computed at most once. When dfs(i, j) is called and memo[i][j] is already set, we return memo[i][j] immediately without re-exploring neighbors. Because the graph is a DAG (no cycles), the DFS tree for any starting cell is guaranteed to terminate. The total work across all cells is O(m*n) — each cell examines at most 4 neighbors and is the subject of at most one full computation. The final answer is the maximum of dfs(i, j) over all (i, j).

To kick off the computation, iterate over all m*n cells and call dfs(i, j) for each. Cells that were already computed during a previous DFS call (because they were reachable from another starting cell) will return in O(1). The outer loop ensures every cell is considered as a potential path start, so we never miss a path that does not pass through a previously visited starting point.

The topological sort approach treats the matrix as a directed graph where each cell is a node and there is a directed edge from cell A to cell B if B is a neighbor of A and matrix[B] > matrix[A]. In this DAG, we want the length of the longest path, which equals the number of layers in a BFS from all source nodes simultaneously. Source nodes — cells with in-degree 0 in this graph — are the local minima: cells where no neighbor has a smaller value.

The BFS proceeds as follows: compute the in-degree of every cell (count of neighbors with strictly smaller values). Enqueue all cells with in-degree 0 (the local minima). Process each BFS level: dequeue all current-level cells, and for each, visit their outgoing neighbors (cells with strictly greater values). Decrement each neighbor's in-degree by 1. When a neighbor's in-degree reaches 0, enqueue it for the next level. The number of BFS levels processed is the answer.

At the end of the BFS, every cell has been processed exactly once (because the graph is a DAG and the BFS correctly processes all nodes in topological order). The level count equals the longest path length because a node appears at level k if and only if the longest increasing path ending at that node has length k. This is equivalent to the DFS memoization result but expressed iteratively.

Both DFS memoization and BFS topological sort run in O(m*n) time and O(m*n) space. Every cell is visited exactly once in both approaches, and each edge (pair of adjacent cells with a strict order) is examined exactly once from each direction. The space is O(m*n) for the memo table (DFS) or the in-degree array plus BFS queue (BFS). Neither approach has a meaningful asymptotic advantage over the other.

DFS memoization is generally preferred in interviews because the code is shorter and more intuitive. The recursive structure directly mirrors the problem definition: "the longest path from (i, j) is 1 plus the longest path from the best neighbor." The memoization pattern is also a transferable skill applicable to many other problems (Coin Change, Word Break, Unique Paths with obstacles). The main downside is that deep recursion on a 200x200 grid can hit Python's default recursion limit; you may need sys.setrecursionlimit(200*200) or an iterative DFS.

BFS topological sort shines when the recursion stack is a concern — for example, in environments with small stack sizes, or for very large grids where stack overflow is a real risk. The iterative BFS never risks stack overflow regardless of grid size. It also makes the level-by-level structure explicit, which can be easier to reason about for some people. Choose BFS if you want an iterative solution or if the interviewer specifically asks about avoiding recursion.

Python DFS memoization: def longestIncreasingPath(matrix): if not matrix: return 0; m, n = len(matrix), len(matrix[0]); memo = [[0]*n for _ in range(m)]; dirs = [(0,1),(0,-1),(1,0),(-1,0)]; def dfs(i, j): if memo[i][j]: return memo[i][j]; best = 0; for di, dj in dirs: r, c = i+di, j+dj; if 0<=r<m and 0<=c<n and matrix[r][c] > matrix[i][j]: best = max(best, dfs(r, c)); memo[i][j] = best + 1; return memo[i][j]; return max(dfs(i, j) for i in range(m) for j in range(n)). Time O(m*n), space O(m*n) for memo and recursion stack.

Java DFS memoization: public int longestIncreasingPath(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] memo = new int[m][n]; int ans = 0; for (int i=0; i<m; i++) for (int j=0; j<n; j++) ans = Math.max(ans, dfs(matrix, memo, i, j, m, n)); return ans; } private int dfs(int[][] mat, int[][] memo, int i, int j, int m, int n) { if (memo[i][j] != 0) return memo[i][j]; int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; int best = 0; for (int[] d : dirs) { int r=i+d[0], c=j+d[1]; if (r>=0&&r<m&&c>=0&&c<n&&mat[r][c]>mat[i][j]) best = Math.max(best, dfs(mat, memo, r, c, m, n)); } return memo[i][j] = best + 1; }. Both Python and Java solutions share the same memoized DFS structure with 4-directional exploration.

For the BFS topological sort alternative: compute in-degree for each cell (number of neighbors with strictly smaller value), enqueue all in-degree-0 cells (local minima), then run BFS incrementing a level counter and decrementing in-degrees of downstream neighbors. When a neighbor's in-degree hits 0, add to next-level queue. Return final level count. The BFS version avoids recursion entirely and is safe for the maximum 200x200 grid size.

Number of Islands (LeetCode 200) and Pacific Atlantic Water Flow (LeetCode 417) are both DFS/BFS grid problems that build the same skills: multi-source traversal, visited tracking, and 4-directional exploration. Pacific Atlantic Water Flow in particular uses BFS from two source sets simultaneously — a technique structurally similar to the topological sort BFS in LeetCode 329. Mastering these two problems first makes LeetCode 329 significantly more approachable.

Minimum Path Sum (LeetCode 64) is the classic top-down-left-right grid DP that LeetCode 329 intentionally breaks. Understanding why standard DP ordering works for Minimum Path Sum (fixed dependency direction) but fails for LeetCode 329 (value-dependent direction) is a key conceptual takeaway. If an interviewer asks you to compare these two problems, the answer is: Minimum Path Sum has a fixed DAG order on grid coordinates; LeetCode 329's DAG is determined by cell values and can go any direction.

The matrix DFS memoization family includes Out of Boundary Paths (LeetCode 576), Knight Probability in Chessboard (LeetCode 688), and Unique Paths III (LeetCode 980). All share the pattern of DFS from each starting state with memoization, where the strictly increasing (or similar) constraint ensures no cycles. Longest Increasing Subsequence (LeetCode 300) is the 1D analog: instead of a 2D grid with 4-directional moves, you have a 1D array with forward moves to larger values — the same DAG structure, just one dimension lower.