Longest Increasing Path in a Matrix
hardTime: O(m*n)Space: O(m*n)
Signals to notice
longest increasing path in matrix4-directional movesDFS + memoization
Brute force first
DFS from each cell without caching — exponential.
The key insight
DFS with memo: dp[i][j] = longest path from (i,j). Try 4 neighbors with strictly larger values. Cache results. O(m×n).
What must stay true
Strictly increasing values guarantee no cycles — memoization is safe without a visited set. Each cell computed once.
Easy way to go wrong
Using a visited set — unnecessary and wrong for memoization. The same cell can be part of many paths.