Longest Increasing Path in a Matrix
Longest Increasing Path in a Matrix: find the maximum length of a four-directional path whose values strictly increase.
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2³¹ - 1
Intuition
Longest increasing path in a matrix asks for the longest four-directional path whose values strictly increase. Running a plain DFS from every cell re-explores the same suffixes over and over and is exponential.
The property that makes memoisation valid is easy to overlook but essential: because every step must go to a strictly larger value, a path can never return to a cell it has already used. Values would have to decrease at some point to close a loop, and that is forbidden.
- The strict increase means the grid is acyclic — an implicit DAG — so no visited-set is needed and results can be cached safely.
That matters because it is exactly what separates this from a general graph problem. In a cyclic graph you cannot memoise a DFS result while the search is still in progress; here you can.
So define dfs(r, c) as the length of the longest increasing path starting at that cell. Its value is 1 plus the best result among the strictly larger neighbours, or just 1 if no neighbour qualifies. Every cell's answer depends only on cells with larger values, so it is well-defined and computed once.
Cache the result on first computation. Each cell is then evaluated once and read many times, and the answer is the maximum over all starting cells. That gives O(rows × cols) — every cell computed once, each doing constant work over its four neighbours.
When moves must strictly increase or decrease, the values themselves impose a DAG even if the grid has undirected adjacency. Memoized DFS is a compact way to compute longest paths in that implicit DAG.
Approach
Before reading on: price up what the direct approach costs here, then ask which subproblem is being recomputed, and what key identifies it. Aim for O(rows * cols) time and O(rows * cols) space.
Notice the grid is acyclic
Strictly increasing moves cannot form a cycle, since returning to a cell would require a decrease. This makes the grid an implicit DAG, which is what licenses caching a DFS result without any visited-set bookkeeping.
Define the value per starting cell
dfs(r, c) returns the longest increasing path starting at that cell, counting the cell itself. Starting from a cell rather than ending at one is what makes the recurrence depend only on larger neighbours.
Extend only to strictly larger neighbours
Check the four adjacent cells; recurse into any that is in bounds and holds a greater value. The answer is 1 + max(results), or 1 when no neighbour qualifies and the path stops immediately.
Memoise on first computation
Store each cell's result in a cache and return it on later visits. Without this the search is exponential — with it, every cell is computed exactly once regardless of how many paths pass through it.
Try every cell as a start
The longest path can begin anywhere, so run the memoised DFS from every cell and take the maximum. Later calls are nearly free because most of the grid is already cached.
Cost of the memoised search
Each of the rows × cols cells is computed once with constant work over four neighbours, giving O(rows × cols) time and the same for the cache. Recursion depth can reach the number of cells on a monotone grid, which is the one case where an explicit stack helps.
Solution & live demo
Common pitfalls
Allowing equal-valued moves
matrix[nr][nc] >= matrix[row][col]
matrix[nr][nc] > matrix[row][col]
The path must be strictly increasing.
Forgetting to count the current cell
best = 0
best = 1
A cell with no larger neighbor still forms a length-one path.
Using one global visited set
if (row, col) in visited:
return 0@cache def dfs(row, col):
Cells may belong to many candidate paths; their optimal suffix should be reused, not forbidden.
Edge cases
The cell alone forms a path of length one.
Strict comparison permits no move, so every cached length is one.
Four-directional DFS explores turns without imposing row or column order.