329. Longest Increasing Path in a Matrix
329. Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
DFS
---
---
---
Intuition
If a neighboring cell is less than current cell, there is a potential path from neighbor to current.
Number of neighbors smaller than current - number of potential paths coming into current ~ inDegree
if inDegree of current is 0 => no neighbor is smaller than me at this time. So current cell is potential starting point
Once we have initial set of starting points, we can run BFS / topological sort
Initial / starting points are smallest elements with 0 inDegree => all neighbors greater or equal
For each node at current level, check if neighbor is greater, and reduce its inIndegree
If indegree of neighbor is 0, means, no other neighbor of new point is smaller, this neighbor is candidate for next level of BFS, add it to Queue.
Why does this BFS approach work to find longest path.
No path can start in the middle of BFS as inDegree nodes with 0 are part of 1st level nodes
On the other hand if some path started at beginning ends mid way, thats ok, because BFS will continue till the whole level is exhausted, and no new greater neighbors are found
So number of levels traversed is the length of longest path
---
Time - O ( M * N )
Space - O ( M * N )
---
Intuition
If a neighboring cell is less than current cell, there is a potential path from neighbor to current.
Number of neighbors smaller than current - number of potential paths coming into current ~ inDegree
if inDegree of current is 0 => no neighbor is smaller than me at this time. So current cell is potential starting point
Once we have initial set of starting points, we can run BFS / topological sort
Initial / starting points are smallest elements with 0 inDegree => all neighbors greater or equal
For each node at current level, check if neighbor is greater, and reduce its inIndegree
If indegree of neighbor is 0, means, no other neighbor of new point is smaller, this neighbor is candidate for next level of BFS, add it to Queue.
Why does this BFS approach work to find longest path.
No path can start in the middle of BFS as inDegree nodes with 0 are part of 1st level nodes
On the other hand if some path started at beginning ends mid way, thats ok, because BFS will continue till the whole level is exhausted, and no new greater neighbors are found
So number of levels traversed is the length of longest path
---
Time - O ( M * N )
Space - O ( M * N )
---
