Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Increasing Path in a Matrix
Bookmark
Brute Force DFS
Memoized DFS
Topological Peel
Input
Example 1 (ans=4)
Example 2 (ans=4)
Single Cell
2x2 Spiral
3x3 Mixed
Custom
matrix
=
[[9,9,4],[6,6,8],[2,1,1]]
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
best = -
longest = 0
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
best = -
longest = 0
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
(0,3) is off the grid
best = 1
longest = 1
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
longest so far = 2
best = 2
longest = 2
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
dfs(1, 2) on value 8
best = 2
longest = 2
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
start a fresh walk at (1,2)
best = 2
longest = 2
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
dfs(0, 0) on value 9
best = 1
longest = 2
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
(3,0) is off the grid
best = 3
longest = 3
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
dfs(1, 1) on value 6
best = 3
longest = 3
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
1 + 1 = 2 via (0,1)
best = 3
longest = 3
step only to a strictly larger neighbour
9
9
4
6
6
8
2
1
1
longest increasing path = 4
best = -
longest = 4
algo
master
.
io
Step:
Longest Increasing Path in a 3x3 matrix. From any cell you may step to a strictly larger 4-directional neighbor.
0 / 194
Input
Example 1 (ans=4)
Example 2 (ans=4)
Single Cell
2x2 Spiral
3x3 Mixed
Custom
matrix
=
[[9,9,4],[6,6,8],[2,1,1]]
0 / 194
algo
master
.
io
Step:
Longest Increasing Path in a 3x3 matrix. From any cell you may step to a strictly larger 4-directional neighbor.
