By Long Luo

Here shows 4 Approaches to slove this problem: BFS, Memorization DFS, DP, Topological Sorting.

# BFS

The simplest method that comes to my mind is BFS. We start search from each node, spread out like water, to see how far it can flood, and record the maximum flood path length of all nodes.

## Analysis

• Time Complexity: $O(m^2n^2)$.
• Space Complexity: $O(mn)$.

# Memory + DFS

It’s easy to figure out that there are some repeated enqueuing in BFS method.

Take a example, when searching the longest path of $2$, the longest path of $6$ will also be searched. However, we will search $6$ again as a starting node in BFS.

So how to prune the search?

If we search $6$ first and store the result. When search $2$, we can know the result is $len(2) + len(6)$.

So we can use a memory to store the result, use DFS to search the longest path of each node.

## Analysis

• Time Complexity: $O(mn)$.
• Space Complexity: $O(mn)$.

# DP

We can also use the DP to solve this problem.

$dp[i][j]$ means the longest path from the position of $matrix[i][j]$.

The DP tranfer equation is as follows:

$dp[i][j] = max(dp[i][j], dp[nextX][nextY] + 1), matrix[nextX][nextY] > matrix[i][j]$

1. At the beginning, all the node is $1$.
2. We should search the larger adjacent nodes first.

## Analysis

• Time Complexity: $O(mnlog(mn)$.
• Space Complexity: $O(mn)$.

# Topo Sorting

Consider the matrix as a directed graph, and calculate the out-degree corresponding to each cell, how many edges start from the cell.

If the value of a cell is smaller than the value of all adjacent cells, so the out-degree of the cell will increate.

We can solve this problem using topo sorting.

## Analysis

• Time Complexity: $O(mn)$.
• Space Complexity: $O(mn)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗