Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Increasing Path in a Matrix
Bookmark
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]]
level
-
longest =
-
9
9
4
6
6
8
2
1
1
step to any larger 4-directional neighbor; find the longest increasing chain
level
-
longest =
-
9
9
4
6
6
8
2
1
1
step to any larger 4-directional neighbor; find the longest increasing chain
level
1
longest =
1
9
in:1
9
in:2
4
L1
6
in:1
6
in:1
8
in:3
2
in:1
1
L1
1
L1
in-degree 0
cells are local minima, the start of every path =
level 1
level
1
longest =
1
9
in:1
9
in:1
4
L1
6
in:1
6
in:1
8
in:2
2
in:1
1
L1
1
L1
(0,2) = 4
relaxes larger neighbors
level
1
longest =
1
9
in:1
9
in:1
4
L1
6
in:1
6
L2
8
in:1
2
L2
1
L1
1
L1
level 1 peeled; the wave moves to level 2
level
2
longest =
3
9
in:1
9
in:1
4
L1
6
L3
6
L2
8
in:1
2
L2
1
L1
1
L1
(2,0) = 2
relaxes larger neighbors
→
1 join level 3
level
2
longest =
3
9
in:1
9
L3
4
L1
6
L3
6
L2
8
L3
2
L2
1
L1
1
L1
level 2 peeled; the wave moves to level 3
level
3
longest =
4
9
L4
9
L3
4
L1
6
L3
6
L2
8
L3
2
L2
1
L1
1
L1
(1,0) = 6
relaxes larger neighbors
→
1 join level 4
level
3
longest =
3
9
L4
9
L3
4
L1
6
L3
6
L2
8
L3
2
L2
1
L1
1
L1
level 3 peeled; the wave moves to level 4
level
4
longest =
4
9
L4
9
L3
4
L1
6
L3
6
L2
8
L3
2
L2
1
L1
1
L1
(0,0) = 9
relaxes larger neighbors
level
4
longest =
4
9
L4
9
L3
4
L1
6
L3
6
L2
8
L3
2
L2
1
L1
1
L1
longest increasing path =
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 / 20
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 / 20
algo
master
.
io
Step:
Longest Increasing Path in a 3x3 matrix. From any cell you may step to a strictly larger 4-directional neighbor.
