HardNeetCode150Depth-First SearchDynamic 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.
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
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