HardNeetCode150Depth-First SearchBreadth-First SearchGraphTopological SortDynamic ProgrammingMatrix
Longest Increasing Path in a Matrix
Find length of longest increasing path.
Examples
Input
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output
4
Path: 1->2->6->9 or 1->2->6->9.
Constraints
- •
m,n <= 20 - •
0 <= matrix[i][j] <= 2^31
Approaches
DFS from each cell.
CodeT: O(m*n * 4^(m*n)) | S: O(m*n) stack
Cache results per cell.
CodeT: O(m*n) | S: O(m*n) memo
def longestIncreasingPath(matrix):
if not matrix: return 0
r,c=len(matrix),len(matrix[0]); memo={}
def dfs(i,j):
if (i,j) in memo: return memo[(i,j)]
mx=1
for di,dj in [(1,0),(-1,0),(0,1),(0,-1)]:
ni,nj=i+di,j+dj
if 0<=ni<r and 0<=nj<c and matrix[ni][nj]>matrix[i][j]:
mx=max(mx,1+dfs(ni,nj))
memo[(i,j)]=mx
return mx
return max(dfs(i,j) for i in range(r) for j in range(c))BFS from cells with no smaller neighbor.
CodeT: O(m*n) | S: O(m*n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS Brute | O(m*n * 4^(m*n)) | O(m*n) stack | DFS from each cell. |
| DFS + Memoization | O(m*n) | O(m*n) memo | Cache results per cell. |
| Topological Sort | O(m*n) | O(m*n) | BFS from cells with no smaller neighbor. |
DFS Brute
T: O(m*n * 4^(m*n))S: O(m*n) stack
DFS from each cell.
DFS + Memoization
T: O(m*n)S: O(m*n) memo
Cache results per cell.
Topological Sort
T: O(m*n)S: O(m*n)
BFS from cells with no smaller neighbor.
Common Mistakes
Not memoizing results
Wrong direction check
Not handling single cell