# Longest Increasing Path in a Matrix (Practice 5069): Brief

Interviewers use this pattern to test whether you can state the invariant before coding. Here is a compact rehearsal note.

## Approach

Memoized DFS from every cell; strictly increasing edges make the graph a DAG so no visited set is needed.

```python
from functools import lru_cache
def longest_increasing_path(m):
R,C=len(m),len(m[0])
@lru_cache(None)
def dfs(r,c):
best=1
for x,y in((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
if 0<=xm[r][c]: best=max(best,1+dfs(x,y))
return best
return max(dfs(r,c) for r in range(R) for c in range(C))
```

## Complexity

Linear in the dominant input size for the scan; heap/tree variants add a log factor.

## Interview pitfalls

State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.

## Practicing out loud

Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see www.linkjob.ai.