Longest Increasing Path in a Matrix
hardTime: O(m*n)Space: O(m*n)
Recognize the pattern
longest increasing path in matrix4-directional movesDFS + memoization
Brute force idea
DFS from each cell without caching — exponential.
Better approach
DFS with memo: dp[i][j] = longest path from (i,j). Try 4 neighbors with strictly larger values. Cache results. O(m×n).
Key invariant
Strictly increasing values guarantee no cycles — memoization is safe without a visited set. Each cell computed once.
Watch out for
Using a visited set — unnecessary and wrong for memoization. The same cell can be part of many paths.