Longest Increasing Path in a Matrix

Given a matrix of integers, return the length of the longest strictly increasing path where you may move up, down, left, or right. Pattern focus: Only valid on DAGs. Once you view each cell as a node and larger neighbors as outgoing edges, the graph becomes a DAG.

Input Format

matrix = integer grid

Output Format

length of the longest strictly increasing path

Constraints

  • 1 <= matrix.length, matrix[0].length <= 200
  • -10^9 <= matrix[i][j] <= 10^9

Examples

Example 1:

Input:

matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output:

4

Explanation:

One longest path is 1 -> 2 -> 6 -> 9.

Example 2:

Input:

matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output:

4

Explanation:

One longest path is 3 -> 4 -> 5 -> 6.

Example 3:

Input:

matrix = [[1]]

Output:

1

Explanation:

A single cell contributes a path of length 1.

Loading...
Longest Increasing Path in a Matrix