Given an m x n integer matrix, return the length of the longest strictly increasing path, moving between orthogonally adjacent cells (up, down, left, right).
Example
Input matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output 4
Key Pointers
A DFS from any cell, only stepping to strictly greater neighbors, gives the longest increasing path starting there — and that answer never changes no matter what triggered the DFS, which is exactly what makes it memoizable.
No visited set is needed during the DFS: since every step must strictly increase in value, a path can never loop back on itself.
Memoizing per cell turns what looks like an exponential search into O(rows · cols) total work, since each cell's DFS runs to completion only once.
Step-by-Step Analysis
Create a memo grid the same size as the matrix, initialized to 0 (meaning "not yet computed").
Define dfs(r, c): if memo[r][c] is already set, return it.
Otherwise, try all 4 neighbors; for each one with a strictly greater value, recurse into it and track the best result.
The cell's answer is 1 plus the best neighbor result (or just 1, if no neighbor qualifies) — store it in memo[r][c] before returning.
Run dfs from every cell in the matrix and return the overall maximum.
Complexity
Time: O(m · n) — Space: O(m · n)
Code
def longestIncreasingPath(matrix: list[list[int]]) -> int:
rows, cols = len(matrix), len(matrix[0])
memo = [[0] * cols for _ in range(rows)]
def dfs(r: int, c: int) -> int:
if memo[r][c]:
return memo[r][c]
best = 1
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[r][c] = best
return best
return max(dfs(r, c) for r in range(rows) for c in range(cols))
Code Explanation
How the solution above works, piece by piece.
dfs(r, c) = length of the longest strictly increasing path that starts at (r, c).
If already computed, return the memo.
Otherwise it's 1 (the cell itself) plus the best dfs of any neighbour with a larger value.
Strictly increasing paths can't form cycles, so memoising is safe and no visited set is needed.
Each cell is solved once: O(rows × cols) time and space.
Visual Walkthrough
Running it on matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]:
Each cell's value in the memo is 1 plus the best memo of a strictly larger neighbour. Because a path must strictly increase it can never loop back, so each cell is solved once and cached. The longest path, 1 → 2 → 6 → 9, has length 4.